101. Path Sum II

Walk every root-to-leaf path with DFS. Carry the remaining target down; append each node's value to the current path on the way in and pop it on the way out. At a leaf, record the path if the remaining target hit zero.

Explore every root-to-leaf path

Run a depth-first search that carries the current path and how much of the target is left (remaining). Add the node value entering, subtract it from remaining, and undo both when leaving (backtracking) so sibling paths aren't polluted.

def dfs(node, remaining, path):
    if not node: return
    path.append(node.val); remaining -= node.val
    if node is a leaf and remaining == 0:
        record a copy of path
    else:
        dfs(node.left,  remaining, path)
        dfs(node.right, remaining, path)
    path.pop()          # backtrack

Only record at leaves (both children null) — an interior node hitting zero doesn't count.

Worked example

Tree [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22.

Two root-to-leaf paths sum to 22:

• 5 -> 4 -> 11 -> 2 (5+4+11+2 = 22)
• 5 -> 8 -> 4 -> 5 (5+8+4+5 = 22)

So the answer is [[5,4,11,2], [5,8,4,5]].

Complexity

• Time: O(n^2) worst case (copying each recorded path of length up to n).
• Space: O(n) for the recursion and current path.

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), res);
        return res;
    }

    private void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        remaining -= node.val;
        if (node.left == null && node.right == null && remaining == 0) {
            res.add(new ArrayList<>(path));
        } else {
            dfs(node.left, remaining, path, res);
            dfs(node.right, remaining, path, res);
        }
        path.remove(path.size() - 1);
    }
}