# Simple AC Java Solution DFS

• 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;
}``````

• same question, about the time complexity~

• @yuhengw it is O(n^2)

• @elmirap Not exactly.

If the tree is balanced, then each node is reached from its ancestors (+ itself) only, which are up to `log n`. Thus, the time complexity for a balanced tree is `O (n * log n)`.

However, in the worst-case scenario where the binary tree has the same structure as a linked list, the time complexity is indeed `O (n ^ 2)`.

• @ivtoskov Agree with you, thanks!

• amazing solution

• superb solution

• Javascript solution for recursion version:

``````var pathSum = function(root, sum) {
if(!root) {
return 0;
}
return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
};

var findPath = function(root, sum) {
var res = 0;
if(!root) return res;
if(sum == root.val) res++;
res += findPath(root.left, sum-root.val) + findPath(root.right, sum - root.val);
return res;
}
``````

• Treat each node as root, check subtree sum.

``````    public int pathSum(TreeNode root, int sum) {
if(root == null) return 0;
int count = 0;
count += pathSum(root.left, sum);
count += pathSum(root.right, sum);
count += sum(root, sum);
return count;
}

int sum(TreeNode node, int sum){
if(node == null) return 0;
sum = sum - node.val;
int count = 0;
if(sum == 0) count++;
count += sum(node.left, sum);
count += sum(node.right, sum);
return count;
}``````

• amazing solution

• I have a question about id the path is from the grandchild of root to the end?

• and why the key is sum - target instead of target - sum

• ``````    map.put(sum, map.get(sum)-1);   //Remove the current node so it wont affect other path
return res;
``````

The size remains O(n). To reduce to O(h), you should remove the sum.

``````if(map.get(sum) == 0) map.remove(sum);
return res;``````

• why need two function， these two functions looks similar. could them be merge into one.

'''

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

'''

• @newdev Your solution is incorrect. It counts paths that are not connected.

• @star1993 Could you explain why it is O(NlogN) for balanced binary tree? Thank you.

• @ivtoskov What does the n mean? The number of nodes in tree?

• Why would BFS solution not work, i.e iterating through BFS and then finding the possibile paths from each node.

class Solution {
static int counter=0;
public int pathSum(TreeNode root, int sum) {
if (root==null) return 0;
while (!q.isEmpty()){
TreeNode curr = q.remove();
int x=sup(curr, sum);
System.out.println(x);
counter+=x;
}
return counter;
}

``````public int sup(TreeNode curr, int sum){
int f=0;
if (curr.val==sum) f++;
if (curr.left== null && curr.right==null && curr.val!=sum) return 0;
int left=0;
int right=0;

if (curr.left != null) {
left = sup(curr.left, sum-curr.val);
}
if (curr.right != null) {
right = sup(curr.right, sum-curr.val);
}

return f+left+right;

}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.