# Easy to understand Java solution with comment.

• Any suggestion is greatly appreciated.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

/*
for each parent node in the tree, we have 2 choices:
1. include it in the path to reach sum.
2. not include it in the path to reach sum.

for each child node in the tree, we have 2 choices:
1. take what your parent left you.
2. start from yourself to form the path.

one little thing to be careful:
every node in the tree can only try to be the start point once.

for example, When we try to start with node 1, node 3, as a child, could choose to start by itself.
Later when we try to start with 2, node 3, still as a child,
could choose to start by itself again, but we don't want to add the count to result again.
1
\
2
\
3

*/
public class Solution {
int target;
Set<TreeNode> visited;
public int pathSum(TreeNode root, int sum) {
target = sum;
visited = new HashSet<TreeNode>();  // to store the nodes that have already tried to start path by themselves.
return pathSumHelper(root, sum, false);
}

public int pathSumHelper(TreeNode root, int sum, boolean hasParent) {
if(root == null) return 0;
//the hasParent flag is used to handle the case when parent path sum is 0.
//in this case we still want to explore the current node.
if(sum == target && visited.contains(root) && !hasParent) return 0;
if(sum == target && !hasParent) visited.add(root);
int count = (root.val == sum)?1:0;
count += pathSumHelper(root.left, sum - root.val, true);
count += pathSumHelper(root.right, sum - root.val, true);
count += pathSumHelper(root.left, target , false);
count += pathSumHelper(root.right, target, false);
return count;
}
}``````````

• I totally had the same idea with yours. But the my output was always greater than the expected answer. Now I understand that some child nodes have started several times. Thank you for your explanation. It really helped.

• @jlchen You are welcome. Bu ke qi~~

• @jlchen I met same problem like yours, now I know I need a visited hash set to avoid duplicates, learnt a lot here!

• So what's the time complexity with this method?

• @tankztc I think it is exponential, O(2^n)?

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