/**
 * 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 {
    //计算所有路径和为targetSym的路径：深度优先搜索
    //定义函数rootSum 用来计算以某个节点为起点时的路径和为targetSum的条数
    //pathSum函数递归调用自身，遍历所有节点；
    // 时间复杂度O(N^2),空间复杂度(N)
    // 采用前缀和的方式，时间复杂度O(N),空间复杂度O(N)
    // 采用先序遍历的方式用hashmap记录所有路径和，若遍历当前节点时，hashmap中存在路径和-targetsum
    // 说明此路径中存在某个节点到当前节点的路径和为target
    // 最后需要回溯，防止影响到其他节点
    public int pathSum(TreeNode root, long targetSum) { // taegetSum 会溢出，需要改为long
       Map<Long, Integer> prefix = new HashMap<>();
       prefix.put(0L, 1); // 为了处理路径和刚好等于targetSum的特殊情况
       return dfs(root, prefix, 0, targetSum);
    }
    public int dfs(TreeNode node, Map<Long, Integer> prefix, long curr,long targetSum) {
       if (node == null) {
        return 0;
       }
       int count = 0;
       curr += node.val;
       count = prefix.getOrDefault(curr - targetSum, 0);
       prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
       count += dfs(node.left, prefix, curr, targetSum);
       count += dfs(node.right, prefix, curr, targetSum);
       prefix.put(curr, prefix.get(curr) - 1); // 递归返回后，减少技术，防止影响其他路径的搜索
       return count;
    }
}