Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values along the path equals targetSum.
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 root-to-leaf paths sum to 22.
The number of nodes is in the range [0, 5000]-1000 <= Node.val <= 1000This is DFS with backtracking: build up a path as you descend, and undo that addition when you backtrack up.
A leaf is a node with no left AND no right child — that's your termination check for 'is this a complete path.'
You need a NEW copy of the current path list when you find a valid one — reusing the same mutable list reference means every collected answer would end up referencing the same (later-mutated) list.
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, long remaining, List<Integer> path, List<List<Integer>> result) {
if (node == null) return;
path.add(node.val);
remaining -= node.val;
if (node.left == null && node.right == null && remaining == 0) {
result.add(new ArrayList<>(path)); // COPY — path keeps mutating as the DFS continues
} else {
dfs(node.left, remaining, path, result);
dfs(node.right, remaining, path, result);
}
path.remove(path.size() - 1); // backtrack: undo this node's contribution before returning to the caller
}Time: O(n^2) worst case (path copies), O(n log n) average for a balanced tree · Space: O(h)