437. 路径总和 III

class Solution {

    public int pathSum(TreeNode root, int targetSum) {
        if (root==null){
            return 0;
        }
        int count =dfs(root,targetSum);
        int countLeft = pathSum(root.left, targetSum);
        int countRight=pathSum(root.right,targetSum);
        return count+countLeft+countRight;
    }

    /**
     * 以curr为起点的连续路径是否有结点和为targetSum的数
     * count当前起点和为tarsum的值个数
     */
    private int dfs(TreeNode root, int targetSum) {
        if (root==null){
            return 0;
        }
        targetSum-=root.val;

        //当前结点是否已满足条件
        int curr=0;
        if (targetSum==0){
            curr=1;
        }

        //这里不能加currVal>targetSum或者root.val>targetSum因为咱注意到里面有负数，人家后面还是有希望翻盘的

        return curr+dfs(root.left,targetSum)+dfs(root.right,targetSum);
    }
}