Path Sum III

The key insight mirrors the "subarray sum equals K" array problem. As we traverse from root to a node, we maintain a running prefixSum. If prefixSum - targetSum was seen earlier on this root-to-node path, then the subpath between that earlier node and the current node sums to targetSum.

We store each prefix sum's frequency in a HashMap. We seed it with {0: 1} to handle paths starting from the root.

Algorithm:

• Initialize prefixCount = {0: 1} and prefixSum = 0.
• At each node, add its value to prefixSum.
• Look up prefixSum - targetSum in the map: that count is added to the result.
• Increment the count of prefixSum in the map.
• Recurse on left and right children.
• Backtrack: decrement the count of prefixSum before returning.

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0L, 1); // base case: empty path
    return dfs(root, 0L, targetSum, prefixCount);
}

private int dfs(TreeNode node, long prefixSum, int target,
                Map<Long, Integer> prefixCount) {
    if (node == null) return 0;

    prefixSum += node.val;

    // how many times (prefixSum - target) appeared earlier on this path
    int count = prefixCount.getOrDefault(prefixSum - target, 0);

    // record current prefix sum
    prefixCount.merge(prefixSum, 1, Integer::sum);

    count += dfs(node.left,  prefixSum, target, prefixCount);
    count += dfs(node.right, prefixSum, target, prefixCount);

    // backtrack — remove current prefix sum contribution
    prefixCount.merge(prefixSum, -1, Integer::sum);

    return count;
}

• Time: O(n). Each node is visited exactly once; HashMap operations are O(1) average.
• Space: O(n). The HashMap stores at most O(h) entries at any point (h = tree height), but O(n) in total across the full traversal due to backtracking. Recursion stack is O(h).