Path Sum III

1private int answer;
2private Map<Long, Integer> prefixCount;
3
4public int pathSum(TreeNode root, int targetSum) {
5    answer = 0;
6    prefixCount = new HashMap<>();
7    prefixCount.put(0L, 1);  // Base case: empty path
8    dfs(root, 0L, targetSum);
9    return answer;
10}
11
12private void dfs(TreeNode node, long currSum, int target) {
13    if (node == null) {
14        return;
15    }
16
17    // Count paths ending at this node
18    currSum += node.val;
19    long needed = currSum - target;
20    int pathsFound = prefixCount.getOrDefault(needed, 0);
21    answer += pathsFound;
22
23    // Add current sum to prefix map
24    prefixCount.put(currSum, prefixCount.getOrDefault(currSum, 0) + 1);
25
26    // Recurse into left and right
27    dfs(node.left, currSum, target);
28    dfs(node.right, currSum, target);
29
30    // Backtrack: remove current sum
31    prefixCount.put(currSum, prefixCount.get(currSum) - 1);
32}