437 path sum III

https://leetcode.com/problems/path-sum-iii/

prefix sum + dfs的题，有意思，注意有相同psum的path可能有多个，update count的时候要全加上。还有path只能往下，所以向上返回时要把当前psum扣掉。最后注意overflow。

/**
 * 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 {
    int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        dfs(root, (long)0, targetSum,new HashMap<>());
        return count;
    }
    private void dfs(TreeNode node, long sum, int target, Map<Long, Integer> psum) {
        if (node == null) {
            return;
        }
        sum += node.val;
        // sum - psum = target
        if (sum == target) {
            count++;
        }
        if (psum.containsKey(sum-target)) {
            count+=psum.get(sum-target);
        }
        psum.put(sum, psum.getOrDefault(sum,0)+1);
        dfs(node.left, sum, target, psum);
        dfs(node.right, sum, target,psum);
        psum.put(sum, psum.get(sum)-1);
        if (psum.get(sum)==0) {
            psum.remove(sum);
        }
    }
}