Each time find all the path start from current node

Then move start node to the child and repeat.

Time Complexity should be O(N^2) for the worst case and O(NlogN) for balanced binary Tree.

```
public class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
public int findPath(TreeNode root, int sum){
int res = 0;
if(root == null)
return res;
if(sum == root.val)
res++;
res += findPath(root.left, sum - root.val);
res += findPath(root.right, sum - root.val);
return res;
}
}
```

A better solution is suggested in 17ms O(n) java prefix sum 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:

```
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); //Default sum = 0 has one count
return backtrack(root, 0, sum, map);
}
//BackTrack one pass
public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){
if(root == null)
return 0;
sum += root.val;
int res = map.getOrDefault(sum - target, 0); //See if there is a subarray sum equals to target
map.put(sum, map.getOrDefault(sum, 0)+1);
//Extend to left and right child
res += backtrack(root.left, sum, target, map) + backtrack(root.right, sum, target, map);
map.put(sum, map.get(sum)-1); //Remove the current node so it wont affect other path
return res;
}
```