Path Sum II

mediumAmazon-tagged: Trees & Matrix (mock day)129 stepsJava · Python · C++

Find every root-to-leaf path whose values sum to the target. DFS while keeping the current path and the remaining sum; at a leaf with remaining 0, save a copy of the path. Remove the node from the path when returning.

▶ Watch the animated trace

Traced input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22 → [[5, 4, 11, 2], [5, 8, 4, 5]]. Original problem: leetcode.com/problems/path-sum-ii/

Complexity

BestO(n)

AverageO(n log n)

WorstO(n²)

SpaceO(h)

Copying each found path costs up to O(h).

Key idea

Subtract each node's value from the remaining target on the way down.
Only leaves can end a path.
Backtrack: remove the last node from the path after exploring a node.

Common mistakes

Saving a path at a non-leaf node whose running sum happens to match.
Adding path instead of new ArrayList<>(path).
Pruning when the sum exceeds the target is wrong with negative values.

Solution

Java

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

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

Python

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    res, path = [], []

    def dfs(node: Optional[TreeNode], remain: int) -> None:
        if not node: return
        path.append(node.val)
        remain -= node.val
        if not node.left and not node.right and remain == 0: res.append(path[:])
        dfs(node.left, remain)
        dfs(node.right, remain)
        path.pop()

    dfs(root, targetSum)
    return res

C++

void dfs(TreeNode* node, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (!node) return;
    path.push_back(node->val);
    remain -= node->val;
    bool leaf = !node->left && !node->right;
    if (leaf && remain == 0) res.push_back(path);
    dfs(node->left, remain, path, res);
    dfs(node->right, remain, path, res);
    path.pop_back();
}

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> res;
    vector<int> path;
    dfs(root, targetSum, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty tree No root-to-leaf paths at all.	`root = [], targetSum = 0`	`[]`
Negative values No early pruning, so negatives work.	`root = [-2, null, -3], targetSum = -5`	`[[-2, -3]]`
Match at a non-leaf Node 1 isn't a leaf, so it can't end a path.	`root = [1, 2], targetSum = 1`	`[]`