113. Path Sum II
Given the root of a binary tree (nodes have an integer val and left/right children) and an integer targetSum, gather every root-to-leaf path whose values total exactly targetSum. Each path is reported as the list of node values from the root down to the leaf.
A leaf is a node with no children, and only complete root-to-leaf walks qualify. Report the paths in the order a depth-first traversal that always explores left before right discovers them — this makes the expected output unique. If nothing qualifies, return an empty collection.
Your function receives the root (possibly None/null) and targetSum, and returns a list of value lists.
Example 1:
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]
Explanation: Two complete paths reach 22: 5 → 4 → 11 → 2 in the left subtree and 5 → 8 → 4 → 5 in the right. The left-subtree path is discovered first.
Example 2:
Input: root = [1, 2, 3], targetSum = 5
Output: []
Explanation: The root-to-leaf totals are 3 and 4; nothing sums to 5, so the collection is empty and the grader prints -1.
Constraints:
- 0 ≤ number of nodes ≤ 5000
- -1000 ≤ Node.val ≤ 1000
- -10⁹ ≤ targetSum ≤ 10⁹
Hints:
You need the actual paths, not just a yes/no — carry the walk-so-far with you as you descend, and only commit it when a leaf completes the target.
Backtracking: append the node's value to one shared buffer, recurse left then right, then pop before returning. Copy the buffer into the results at a qualifying leaf — storing the buffer itself would let later pops corrupt it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Expected output: [[5, 4, 11, 2], [5, 8, 4, 5]]