leetcode 路径总和III java

参考leetcode上大神的思路：https://leetcode.cn/problems/path-sum-iii/solutions/596361/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6，添加了自己的注释。
前缀和为Long类型 Map<Long,Integer> prefixSumCount = new HashMap<>();
recur函数里要有prefixSumCount和targetSum,或者宏观定义一下。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution { 
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0L,1);
        //prefixMap: key--前缀和 value--前缀和的节点数量
        return recur(root,prefixSumCount,targetSum,0L);
    }

    private int recur(TreeNode node, Map<Long, Integer> prefixSumCount, int targetSum, Long curSum){
        if(node == null){
            return 0;
        }
        int res = 0;
        curSum += node.val;

        //看看之前的前缀和有没有为curSum-targetSum的
        res += prefixSumCount.getOrDefault(curSum-targetSum,0);
        //更新key为curSum的value值
        prefixSumCount.put(curSum, prefixSumCount.getOrDefault(curSum,0)+1);

        //更新左右子节点
        int left = recur(node.left,prefixSumCount,targetSum,curSum);
        int right = recur(node.right,prefixSumCount,targetSum,curSum);

        res = res+left+right;

        //恢复状态： 在遍历完一个节点的所有子节点后，将其从map中除去。
        prefixSumCount.put(curSum,prefixSumCount.get(curSum)-1);

        return res;
    }

}