Walk down to a leaf with a target
Decide whether some path from the root to a leaf adds up to a target, by subtracting each value as you go down and checking what is left at a leaf. About 12 minutes.
Carry what is still needed
You want to know if some path from the root down to a leaf adds up to a target. At the root, the path must use the root's value, so the rest of the path must add up to the target minus that value.
That is the same question for each child, with a smaller target. So each call subtracts its own value and passes the remainder down. An empty child can never supply a path.
rest = target - root.val # pass rest down to both children
- remaining
- 17
At 5, subtract: 22 − 5 leaves 17 to find below.
Only leaves can answer
A path has to end at a leaf, a node with no children. So the check happens only there: a leaf answers yes when its value equals the target it receives, because nothing more needs to be added.
A node that has one child must not treat the missing child as an end. Without that care, a node with a single child could wrongly end the path in the middle. An empty tree has no path at all, so it answers no.
is_leaf = not root.left and not root.right
A node has a left child but no right child. Its value equals the remaining target. Does the path end here?
- ANo. Only a node with no children can end a path
- BYes, the sum matches
- CYes, if the missing child is null
Show the answer
No. Only a node with no children can end a path. The path must continue down the left child to reach a leaf.
Path sum
Given the root of a binary tree and an integer target, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the target. A leaf is a node with no children. An empty tree has no such path.
root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], target = 22 → true
0 ≤ number of nodes ≤ 5,000 · -1,000 ≤ node.val ≤ 1,000 · -1,000,000 ≤ target ≤ 1,000,000