112. 路径总和（递归）

﹏ヽ暗。殇╰゛Y 2023-10-05 04:18 152阅读 0赞

#### 112. 路径总和 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

说明: 叶子节点是指没有子节点的节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

解题思路：  
这题使用递归解决。题目问的是有没有一条根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 我们可以反向理解，从根节点加到叶子节点的值等于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
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201223230642553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70