250. Path Sum III

A downward path summing to target is a contiguous run on some root-to-node chain. Keep the running prefix sum from the root and a count of how many times each prefix value has occurred. A path ending at the current node with sum target exists once for every earlier prefix equal to (current prefix - target).

Turn a tree path into a prefix-sum count

Any valid path goes strictly downward, so it's a contiguous segment of some root-to-node chain. Let cur be the running sum from the root to the current node. A downward path ending at this node with sum target corresponds to an earlier ancestor whose prefix sum was cur - target.

Maintain a hash map count[prefix] = how many ancestors on the current chain have that prefix sum (seed count[0] = 1 for the empty prefix). At each node:

cur += node.val
answer += count[cur - target]        # paths ending here
count[cur] += 1
dfs(left); dfs(right)
count[cur] -= 1                      # backtrack: leave this chain

The decrement on the way out ensures count only ever reflects the ancestors of the node currently being visited.

Worked example

Tree [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8.

Three downward paths sum to 8:

• 5 -> 3 (root→5→3)
• 5 -> 2 -> 1
• -3 -> 11

So the answer is 3.

Complexity

• Time: O(n) — each node contributes O(1) map work.
• Space: O(h) for the map along the current chain (h = height).

class Solution {
    private int total = 0;
    private int target;

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

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