# 0437. Path Sum III
###### tags: `Leetcode` `FaceBook` `Medium` `Backtracking` `Prefix Sum`
Link: https://leetcode.com/problems/path-sum-iii/
## 思路
问题可以转换成：求解从原始起点（根节点）a到当前节点b的路径中， 有多少节点a满足sum[a...b]=targetSum，由于从原始节点到当前节点的路径唯一，因此是一个一维前缀和问题
由于只能统计向下的路径，但是树的遍历会同时搜索两个方向的子树，因此我们应当在搜索完以某个节点为根的左右子树后，回溯地将路经总和从哈希表中删除，防止统计到跨越两个方向的路径
## Code

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0,1);
        dfs(root, targetSum, 0);
        return ans;
    }
    public void dfs(TreeNode root, int t, int prev){
        if(root == null) return;
        ans += map.getOrDefault(root.val+prev-t,0);
        map.put(root.val+prev, map.getOrDefault(root.val+prev,0)+1);
        dfs(root.left, t, root.val+prev);
        dfs(root.right, t, root.val+prev);
        map.put(root.val+prev, map.get(root.val+prev)-1);
    }
}