Problems
Path Sum II
Medium·Tagstreedfsbacktracking
Problem Statement
Given the `root` of a binary tree and an integer `targetSum`, return all root-to-leaf paths where the sum of the node values in the path equals `targetSum`. Each path should be returned as a list of the node values, not node references.
A leaf is a node with no children.
Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.
Examples
Example 1
Input
root: [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum: 22Tree
Output
"[[5, 4, 11, 2], [5, 8, 4, 5]]"Why
There are two paths whose sum equals 22:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2
Input
root: [1, 2, 3], targetSum: 5Tree
Output
"[]"Why
There are no root-to-leaf paths with sum 5.
Example 3
Input
root: [1, 2], targetSum: 0Tree
Output
"[]"Why
No path exists that equals 0.
Constraints
- •The number of nodes in the tree is in the range [0, 5000].
- •-1000 <= Node.val <= 1000
- •-1000 <= targetSum <= 1000
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
You already know how to verify if a path sum exists using DFS. But now you need to store the actual path. You can do this by passing a `currentPath` array down your recursive function.
Hint 2
When you visit a node, append its value to `currentPath`.
Hint 3
If you reach a leaf node and the remaining sum equals the leaf's value, you found a valid path! But be careful: you cannot just append `currentPath` to your final results array. You must append a *copy* (or clone) of it, because `currentPath` will keep changing as you traverse other branches.
Hint 4
Before your recursive function returns to its parent, you must completely undo the work you did on that node. This is called **Backtracking**. Pop the last node off `currentPath` so the parent can explore a different branch with a clean path state.