# Can anyone help? Java DFS solution but have some problem _(:з」∠)_

• @star1993 hi, actually I have the same idea, but my solution can not figure out whether the subPath is linked together. for example, in the case
[10,5,-3,3,2,null,11,3,-2,null,1]
8
it will return 4 rather than 3, since it count (10) -> (-2) as 1 answer

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

I tried to think of it pvernight but still confusing, can any one help me?

• @monster-gump The way you implemented make it possible to have a broken path, so you have 10-2 = 8 as an answer.. You can check my solution.

• sry, but since I used

``````pathSum(root.left, sum) + pathSum(root.right, sum)
``````

I think it should start from root.left and root.right then, so what's wrong here?
I consider the main problem is that I can't split the connection from the very beginning, which means the maybe some nodes I didn't use for the path, but I don't know how to get rid of them

• @monster-gump Not sure what exactly do you mean... But here are some thoughts:

first,
this is not a valid base case, because we have nodes with negative value.

``````        if (root.val == sum) {
return 1;}
``````

e.g.
[0,1,null,-1]
0
this should return 3, your code would return 1.

second,
broken path

e.g.
[1,2,null,3]
4
this should return 0, your code would return 1.

I'll use the node value to represent the node, and show the call stacks returns 1.
call stack0: pathSum(root.left, sum) -> pathSum(1, 4)
call stack1: pathSum(root.left, sum - root.val) -> pathSum(1.left, 4 - 1) -> pathSum(2, 3)
call stack2: pathSum(root.left, sum) -> pathSum(2.left, 3) -> pathSum(3, 3)
then returns 1.

So you need a way to make sure that the path doesn't split in the middle.

Hope it helps.

• @crickey180 I see.
when I review this question I notice my idea is totally wrong, I just wanted to wrap up everything in the main function but is seems impossible.
your solution is also a smart one.
Thx for explain it in detail.

• @monster-gump You are welcome~

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