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 node values.
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: Both paths 5→4→11→2 and 5→8→4→5 sum to 22.
Input: root = [1,2,3], targetSum = 5
Output: []
Explanation: No root-to-leaf path sums to 5.
Constraints:
- 0 <= Number of nodes <= 5000
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Contents
- Solution — DFS Backtracking
- Complexity Analysis
DFS Backtracking
We extend the Path Sum I approach to collect all valid paths instead of just checking existence.
A mutable currentPath list is maintained. When we reach a valid leaf, a snapshot
(copy) of currentPath is added to the result. The crucial backtracking step is
removing the current node from currentPath before returning.
Algorithm:
- Add the current node's value to currentPath.
- Subtract the node's value from remaining.
- If a leaf is reached and remaining == 0, add a copy of currentPath to results.
- Recurse on left and right children.
- Backtrack: remove the last element from currentPath before returning.
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
dfs(root, targetSum, new ArrayList<>(), result);
return result;
}
private void dfs(TreeNode node, int remaining,
List<Integer> currentPath,
List<List<Integer>> result) {
if (node == null) return;
currentPath.add(node.val);
remaining -= node.val;
if (node.left == null && node.right == null && remaining == 0) {
result.add(new ArrayList<>(currentPath)); // snapshot copy
}
dfs(node.left, remaining, currentPath, result);
dfs(node.right, remaining, currentPath, result);
// backtrack — remove current node before returning to parent
currentPath.remove(currentPath.size() - 1);
}
Always add a copy of currentPath to the result — adding the list directly means later mutations (backtracking) will corrupt the result.
- Time: O(n2) — we visit every node O(n) times; copying a path at a
leaf takes O(n) in the worst case (skewed tree). Overall O(n2) worst case.
- Space: O(n) — currentPath holds at most h elements (tree height),
plus O(h) recursion stack. Output list is not counted in auxiliary space.