Simple AC Java Solution DFS
Each time find all the path start from current node\nThen move start node to the child and repeat. \nTime Complexity should be O(N^2) for the worst case and O(N
Each time find all the path start from current node\nThen move start node to the child and repeat. \nTime Complexity should be O(N^2) for the worst case and O(NlogN) for balanced binary Tree.\n```\npublic class Solution {\n    public int pathSum(TreeNode root, int sum) {\n        if(root == null)\n            return 0;\n        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);\n    }\n    \n    public int findPath(TreeNode root, int sum){\n        int res = 0;\n        if(root == null)\n            return res;\n        if(sum == root.val)\n            res++;\n        res += findPath(root.left, sum - root.val);\n        res += findPath(root.right, sum - root.val);\n        return res;\n    }\n   \n}\n````\nA better solution is suggested in <a href ="https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method"> 17ms O(n) java prefix sum </a> by tankztc. It use a hash map to store all the prefix sum and each time check if the any subarray sum to the target, add with some comments:\n```\n    public int pathSum(TreeNode root, int sum) {\n        Map<Integer, Integer> map = new HashMap<>();\n        map.put(0, 1);  //Default sum = 0 has one count\n        return backtrack(root, 0, sum, map); \n    }\n    //BackTrack one pass\n    public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){\n        if(root == null)\n            return 0;\n        sum += root.val;\n        int res = map.getOrDefault(sum - target, 0);    //See if there is a subarray sum equals to target\n        map.put(sum, map.getOrDefault(sum, 0)+1);\n        //Extend to left and right child\n        res += backtrack(root.left, sum, target, map) + backtrack(root.right, sum, target, map);\n        map.put(sum, map.get(sum)-1);   //Remove the current node so it wont affect other path\n        return res;\n    }
[]