Path Sum III — Prefix Sum HashMap on Tree

# Python
from collections import defaultdict
def pathSum(root, targetSum):
    prefix_count = defaultdict(int)
    prefix_count[0] = 1
    ans = [0]
    def dfs(node, curr_sum):
        if not node: return
        curr_sum += node.val
        ans[0] += prefix_count[curr_sum - targetSum]
        prefix_count[curr_sum] += 1
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)
        prefix_count[curr_sum] -= 1  # backtrack
    dfs(root, 0)
    return ans[0]

// Java
Map<Long,Integer> prefix=new HashMap<>(); int target; int ans=0;
public int pathSum(TreeNode root, int targetSum) {
    target=targetSum; prefix.put(0L,1); dfs(root,0L); return ans;
}
void dfs(TreeNode node, long curr) {
    if (node==null) return;
    curr+=node.val;
    ans+=prefix.getOrDefault(curr-target,0);
    prefix.merge(curr,1,Integer::sum);
    dfs(node.left,curr); dfs(node.right,curr);
    prefix.merge(curr,-1,Integer::sum);
}