How do you solve the path sum problem in a binary tree, and what is the subtlety?
You carry the running total as you walk down the tree, and you look for a leaf where the total is exactly the target.
And what is the subtlety? There are two of them.
The first one is that the path has to end at a leaf. A node in the middle of the tree does not count, even if its running total happens to be the target. So the check for success happens only when both children are nothing.
The second one is that there can be more than one path that works. The question asks whether there is a path, so you stop as soon as you find one. But if the question asks how many paths there are then you have to keep going and add up the answers from both sides.
the tree 5
/ \
4 8
/ / \
11 13 7
the target is 9
the path 5, 4, 11, then the target is not 9, so no
the path 5, 8, 13 gives 13, no
the path 5, 8, 7 gives 7, no
so there is no path that adds up to 9
And the third thing to be careful about is that a node with a value of zero is not the same as a node that is not there. So the check for a leaf cannot just look at whether the value is zero.
And the complexity is O of n for the time, because every node is visited once, and O of h for the space.
So the rule to remember is this. Only a leaf can end a path, and the running total is carried down the tree.
The last question in this topic shows the code.