剑指offer17 JZ82 二叉树中和为某一值的路径(一)

二叉树中和为某一值的路径(一)

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=13&tqId=634&ru=%2Fpractice%2F6e196c44c7004d15b1610b9afca8bd88&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

深度优先遍历+回溯

alt

  1. 首先,深度优点遍历来说,先写上一个回溯 if (curNode == null) { return false; },这表示递归至最深层开始回溯,至于为什么 return false 后面再讲
  2. 每次进入函数时,将 sum 减去当前节点的权重(curNode.val),当 sum 减到零时,说明目标路径存在,另外我们的目标是到叶子节点停止,叶子节点的条件是 curNode.left == null && curNode.right == null,所以说当 if (curNode.left == null && curNode.right == null && target == 0) ,我们返回 true 表示找到目标路径
  3. 深度遍历的分支:对于当前节点 curNode 有两个分支,这两个分支都有可能成为目标路径,所以深度优先遍历的写法为 return dfs(curNode.left, target) || dfs(curNode.right, target);
  4. 现在来谈谈为什么回溯时需要返回 false,因为当 curNode 为叶子节点时,并且 sum == 0 时,我们已经返回了 true,剩下的情况就是 curNode 不是叶子节点或者路径值不为 target,所应该返回 false
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        return dfs(root,sum);
        // write code here
    }
    public boolean dfs(TreeNode cur,int target){
        if(cur==null){
            //回溯
            return false;
        }
        target-=cur.val;
        //减到为0 且为叶子节点 就找到了路径
        if(cur.left==null && cur.right==null && target==0){
            return true;
        }
        //左右节点进行dfs
        return dfs(cur.left,target)||dfs(cur.right,target);
        
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务