Sweaty Imposter

Path Sum III

MediumTree DFSMidOpen on LeetCodeUpdated

You're given the root of a binary tree and an integer targetSum. Return how many paths have node values adding up to targetSum. A path must run downward, parent to child at every step, but it can start at any node and stop at any node below it, so it need not touch the root or a leaf. One node alone is a path. Values can be negative. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 returns 3

105-332113-21
The paths are 5 to 3, 5 to 2 to 1, and -3 to 11.

Three downward paths add to 8: 5 + 3, 5 + 2 + 1, and -3 + 11. None of them starts at the root, and 5 + 3 stops before reaching a leaf.

root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 returns 3

The paths 5 + 4 + 11 + 2 and 5 + 8 + 4 + 5 run from the root to a leaf. The third, 4 + 11 + 7, starts one level below the root.

Constraints

  • 0 <= number of nodes <= 1000
  • -10^9 <= targetSum, node.val <= 10^9

Hints

Hint 1

Paths don't have to start at the root, can a running sum and a lookup help count subpaths ending at each node?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Carry the running sum from the root to the current node, plus a count of each running sum seen on the path above it (seeded with 0 once). A downward path ending here sums to target exactly when some ancestor's running sum equals curr - target, so add that count. Then record curr, recurse into both children, and decrement curr's count on the way back so other branches can't use it. O(n) time, O(n) space for the counts and call stack.

Time

O(n)

Space

O(n)

Pitfall

Forgetting to decrement the running sum's count after both children return, which lets a path join nodes from sibling branches. Seeding the count with 0 once is what makes paths that start at the root count.

Solutions

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, 0L, targetSum, prefix);
    }

    private int dfs(TreeNode node, long curr, int target, Map<Long, Integer> prefix) {
        if (node == null) return 0;
        curr += node.val;
        int count = prefix.getOrDefault(curr - target, 0);
        prefix.merge(curr, 1, Integer::sum);
        count += dfs(node.left, curr, target, prefix);
        count += dfs(node.right, curr, target, prefix);
        prefix.merge(curr, -1, Integer::sum);
        return count;
    }
}
Drill This