Path Sum II — Practice

Problem

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.

Examples

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.

Constraints

•The number of nodes is in the range [0, 5000]
•-1000 <= Node.val <= 1000

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