题目：path-sum-iii

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里 节点值之和 等于 targetSum 的 路径 的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

解题思路

1. 前序遍历二叉树，用 前缀和 统计 当前和-目标和（currSum - targetSum） 在不在缓存里？
2. 注意递归完一个子树，就从缓存里扣除当前的 currSum ，因为从左子树换到右子树了，不再满足路径方向必须向下的前提

---

Java 实现

class Solution {
    // key: 前缀和   value: 该前缀和出现的次数
    Map<Long, Integer> map = new HashMap<>();
    private int count;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null){
            return 0;
        }
        count = 0;
        map.put(0L,1);
        preOrder(root, targetSum, 0L);
        return count;      
    }

    private void preOrder(TreeNode root, int targetSum, long currSum){
        if (root == null){
            return ;
        }
        currSum += root.val;
        if (map.containsKey(currSum - targetSum)){
            count += map.get(currSum - targetSum);
        }
        // 该前缀和是否已经存在 map 中，如果不在，则为 1，否则 +1
        map.compute(currSum, (key, value) -> value == null ? 1 : value + 1);
        preOrder(root.left, targetSum, currSum);
        preOrder(root.right, targetSum, currSum);
        // 递归完一个子树，就从缓存里扣除当前的 currSum
        map.compute(currSum, (key, value) -> value == null ? 0 : value - 1);
    }
}