Path Sum III

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