/**
 * 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 {
    //这一题的路径的定义和普通的路径定义有所差别，它不拘泥于从根节点开始到叶子节点结束的路劲而是可以从任意节点开始到任意节点结束的。
        //这很容易让我们联想到求一个子数组的连续子数组之和为n的做法，使用一个hash表来记录这样一组数据，key代表前n个数据之和，value代表着出现的次数，这样我们查找时只需要判断hash表中是否存在或者说存在几个sum - current值就可以轻松统计了，而且hash表的访问时间复杂度为O（1）
        //所以我们可以这样做任然只要从根节点开始做前序遍历，使用这一方法来判断没条到叶子的路径中到底右几条符合我们条件的路劲就可以轻松统计出所有的值
    public int pathSum(TreeNode root, int targetSum) {
        //初始化hash表
        HashMap<Integer,Integer> map = new HashMap<>(); 
        //初始时0出现过1次
        map.put(0,1);
        //递归出结果
        return getCount(root,map,targetSum,0);
    }

    public int getCount(TreeNode root,HashMap<Integer,Integer> map ,int sum,int path){
        //首先设置递归条件，如果节点为空直接返回0
        if(root == null){
            return 0;
        }
        //叠加path，并且使用path值来判断当前节点是否存在这样的路径
        path += root.val;
        int count = map.getOrDefault(path - sum,0);
        //将当前节点放入到map中
        map.put(path,map.getOrDefault(path,0) + 1);
        //递归得到左右子树的结果
        count += getCount(root.left,map,sum,path);
        count += getCount(root.right,map,sum,path);
        //当前节点已经处理完毕，所以要要从map中退回到没有当前节点的状态
        map.put(path,map.get(path) - 1);
        return count;
    }
}