Root-to-leaf path sum
Explore downward paths, subtracting values along the way, and backtrack when a branch fails. About 8 minutes.
What is a root-to-leaf path?
Think of a family tree and a walk from the oldest ancestor down to someone with no children. That walk is a root-to-leaf path. It starts at the root and ends at a leaf: a node with no left child and no right child.
You want to know whether at least one such walk has node values that add up to the target.
Step on 5: still need 22 − 5 = 17.
Backtracking with remaining sum
Each time you step onto a node, subtract its value from the target, like paying off a bill step by step. When you stand on a leaf and what is left is exactly the leaf's own value, this path wins. Otherwise explore left, then right.
If neither side works the function says no, and the caller quietly tries its other branch. Nothing needs undoing, since the remaining amount is passed down rather than stored.
if not root:
return False
if not root.left and not root.right:
return root.val == target
rem = target - root.val
return (has_path_sum(root.left, rem)
or has_path_sum(root.right, rem))If root has val 5 and left child 3 (a leaf), does has_path_sum with target 8 return true?
- Atrue
- Bfalse
Show the answer
true. The path 5 → 3 is a root-to-leaf path with sum 5 + 3 = 8.
Root-to-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 target. Return false if no such path exists, or if root is null.
root = [5, 4, 8, 11, null, 13, 4, 7, 2], target = 22 → true
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000