class Solution {
    int total = 0;
    public int pathSum(TreeNode root, int sum){
        if(root == null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int pathSumFrom(TreeNode node, int sum){
        if(node == null) return 0;
        int num = 0;
        if(node.val == sum) num++;
        return num + pathSumFrom(node.left, sum-node.val) + pathSumFrom(node.right, sum - node.val); 
    }
}
*/
//preSum map: faster solution
class Solution {
    public int pathSum(TreeNode root, int sum){
        Map<Integer, Integer> preSum = new HashMap<Integer, Integer>();
        preSum.put(0, 1);
        return helper(root, sum, 0, preSum);
    }
    private int helper( TreeNode node, int target, int curSum,  Map<Integer, Integer> preSum ){
        if(node == null) return 0;
        curSum += node.val;
        int count = preSum.getOrDefault( curSum - target, 0 );
        preSum.put(curSum, preSum.getOrDefault(curSum, 0) + 1);
        count += helper(node.left, target, curSum, preSum) + helper(node.right, target, curSum, preSum);
        preSum.put(curSum, preSum.getOrDefault(curSum, 0) -1);
        return count;
    }
}