112. Path Sum
You get the root of a binary tree (nodes carry an integer val plus left and right pointers) together with an integer targetSum. Decide whether some root-to-leaf path — starting at the root and ending at a node with no children — has values that add up to exactly targetSum.
Partial paths never count: even if the running total hits the target halfway down, the walk has to continue to a leaf, and later values change the sum. An empty tree contains no root-to-leaf paths at all, so its answer is always false.
Your function receives the root (possibly None/null) and targetSum, and returns a boolean.
Example 1:
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: The walk 5 → 4 → 11 → 2 ends at the leaf 2 and totals 5 + 4 + 11 + 2 = 22.
Example 2:
Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: The two root-to-leaf paths total 3 (1 → 2) and 4 (1 → 3); neither reaches 5.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -1000 ≤ Node.val ≤ 1000
- -10⁹ ≤ targetSum ≤ 10⁹
Hints:
Every step downward consumes part of the target. After paying the current node's value, what must the subtree below deliver along some path to a leaf?
Recurse with remaining = targetSum - node.val, and succeed only at a leaf whose value equals what is left. Have null nodes return false so a one-child node defers entirely to its real child. Values can be negative, so never prune just because the remaining target dropped below zero.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Expected output: true