Path Sum II

Problem

Given the root of a binary tree and an integer targetSum, return every root-to-leaf path whose node values add up to targetSum. Each path is a list of the node values, from the root down to the leaf.

          5
         / \
        4   8
       /   / \
      11  13  4            targetSum = 22
     /  \    / \
    7    2  5   1          →   [[5,4,11,2], [5,8,4,5]]

A path must start at the root and end at a leaf (a node with no children). Stopping partway down doesn't count.
Node values and targetSum can be negative, so you can't stop exploring early just because the running sum has exceeded the target.
Return an empty list if no path qualifies. This is a classic backtracking problem: build a path, record it if valid, and undo the last step before exploring the next branch.

Hints

Hint 1

This is DFS with backtracking: build up a path as you descend, and undo that addition when you backtrack up.

Hint 2

A leaf is a node with no left AND no right child — that's your termination check for 'is this a complete path.'

Hint 3

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.

Solutions

public List<List<Integer>> pathSumBruteForce(TreeNode root, int targetSum) {
    List<List<Integer>> allPaths = new ArrayList<>();
    collectAllPaths(root, new ArrayList<>(), allPaths);
    List<List<Integer>> result = new ArrayList<>();
    for (List<Integer> path : allPaths) {
        long sum = 0;
        for (int v : path) sum += v;
        if (sum == targetSum) result.add(path);
    }
    return result;
}
private void collectAllPaths(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null) allPaths.add(new ArrayList<>(path));
    else { collectAllPaths(node.left, path, allPaths); collectAllPaths(node.right, path, allPaths); }
    path.remove(path.size() - 1);
}

Time: O(n^2) worst case · Space: O(n) for all collected paths

Problem

          5
         / \
        4   8
       /   / \
      11  13  4            targetSum = 22
     /  \    / \
    7    2  5   1          →   [[5,4,11,2], [5,8,4,5]]

A path must start at the root and end at a leaf (a node with no children). Stopping partway down doesn't count.
Node values and targetSum can be negative, so you can't stop exploring early just because the running sum has exceeded the target.
Return an empty list if no path qualifies. This is a classic backtracking problem: build a path, record it if valid, and undo the last step before exploring the next branch.

Hints

Hint 1

This is DFS with backtracking: build up a path as you descend, and undo that addition when you backtrack up.

Hint 2

A leaf is a node with no left AND no right child — that's your termination check for 'is this a complete path.'

Hint 3

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.

Solutions

public List<List<Integer>> pathSumBruteForce(TreeNode root, int targetSum) {
    List<List<Integer>> allPaths = new ArrayList<>();
    collectAllPaths(root, new ArrayList<>(), allPaths);
    List<List<Integer>> result = new ArrayList<>();
    for (List<Integer> path : allPaths) {
        long sum = 0;
        for (int v : path) sum += v;
        if (sum == targetSum) result.add(path);
    }
    return result;
}
private void collectAllPaths(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null) allPaths.add(new ArrayList<>(path));
    else { collectAllPaths(node.left, path, allPaths); collectAllPaths(node.right, path, allPaths); }
    path.remove(path.size() - 1);
}

Time: O(n^2) worst case · Space: O(n) for all collected paths

Problem

Examples

Constraints

Hints

Solutions

Path Sum II

Problem

Examples

Constraints

Hints

Solutions