437. 路径总和 III

一 题目：

二 思路：

• 递归：每个结点作为开始结点向下寻找和为target的路径
• 注意：
• 1.结点本身可能就值为target
• 2 这里不能过程中返回，因为咱们这个数存在负数，不到null结点都有可能是我们的目标

三 代码：

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);
    }
}