112. 路径总和（递归）

112. 路径总和

• 题目
• 解题思路
• 代码

题目

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

解题思路

解题思路：
这题使用递归解决。题目问的是有没有一条根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 我们可以反向理解，从根节点加到叶子节点的值等于sum，就是满足条件的。那么我们既然有sum的值，我们就可以从根节点出发，每经过一个节点就用sum减去那个节点的值，直到叶子节点。这个时候再判断sum是不是为0.如果为0，证明这条路上节点值的和刚好等于sum。

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){
            return false;
        }

        if(root.left==null&&root.right==null){//当到达叶子节点的时候
            sum=sum-root.val;//到达了叶子节点，还要用sum减去叶子节点的值
            return sum==0;//如果sum为0证明这条路线满足条件
        }

        boolean caseLeft=hasPathSum(root.left,sum-root.val);//遍历左子树，这时候sum应该更新为 “原来的sum减去了根节点的值”
        boolean caseRight=hasPathSum(root.right,sum-root.val);

    return caseLeft||caseRight;//只要左子树或者右子树有一棵树满足sum最后为0，那么就达到目标了，证明存在题目所要求的那么一条路径。  返回true
    }
}