437. 路径总和 III (opens new window)

1.树的前缀和+回溯

• 同一个节点可以同时作为多个路径的起点或者是终点，因此需要回溯。
• 考虑到路径不需要在叶子节点结束，目标路径可能出现在根到叶子完整路径的中间，采用前缀和方法。但是根据上一点，一个节点可能同时作为多条路径的终点，因此不仅需要统计前缀和，还需要统计前缀和出现的次数，故使用哈希保存根节点到当前节点的前缀和。
• 此处前缀和统计的是根节点到当前节点的前缀和，所以不需要用列表保存。直接将父节点的前缀和结果作为形参传递给子节点。

注意节点数据的大小，用int接收会越界。因为提前在哈希中添加了哨兵节点，需要考虑targetSum为0的情况，要注意插入哈希的时机。

class Solution {
    int res=0;
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long,Integer> map=new HashMap<>();
        map.put(0L,1);
        dfs(root,map,targetSum,0L);
        return res;
    }
    public void dfs(TreeNode root,HashMap<Long,Integer> map,int targetSum,Long last){
        if(root==null) return;
        Long prefix=root.val+last;
        res+=map.getOrDefault(prefix-targetSum,0);
        map.put(prefix,map.getOrDefault(prefix,0)+1);
        
        if(root.left!=null){
            dfs(root.left,map,targetSum,prefix);
        }
        if(root.right!=null){
            dfs(root.right,map,targetSum,prefix);
        }
        
        if(map.get(prefix)>1) map.put(prefix,map.get(prefix)-1);
        else  map.remove(prefix);
    }
}