一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 443|回复: 5
收起左侧

[Leetcode] 疑惑求解答:Minimum Depth of Binary Tree

[复制链接] |试试Instant~ |关注本帖
Artemis 发表于 2015-6-15 06:19:48 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        //为什么会有下面这两个if条件句? 感觉这样会导致结果不对啊...
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        else return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }
}

(我在LeetCode自己提交的解答没有那两个if条件句,被判断为Wrong Answer。)
求解~~谢谢!:)
题目链接:https://leetcode.com/problems/minimum-depth-of-binary-tree/
invisibili 发表于 2015-6-15 06:41:57 | 显示全部楼层
比如说有个node 只有右子树 这个node就不是leaf 但是没有那两个if就会把这个node当作leaf然后返回1 结果就错了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-6-15 06:48:29 | 显示全部楼层
作为一个树的话min depth还是相对于节点路径算的,在多条路径中找到最短的那条。不加那两个if的话,如果root的子节点有一个是空的,就直接以那个为结果返回了。

         1
      /     \
    /        \
  2         Null

这个情况下正确的minDepth路径应该是 1 - 2

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laoxie09 发表于 2015-6-15 06:53:27 | 显示全部楼层
本帖最后由 laoxie09 于 2015-6-15 07:13 编辑

we only return the depth when we meet leaf nodes(both left and right kids are null).

In the example(given by @mnmunknown)

         1
      /     \
    /        \
  2         Null

you may return 1 prematurely (for root node only right kid is empty)
Hope this code helps

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        if (root.right == null && root.left == null) return 1;
        if (root.right != null && root.left != null)  return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
        return -1;//just for compile and error check;
    }
}





评分

1

查看全部评分

回复 支持 反对

使用道具 举报

tonyabracadabra 发表于 2015-6-17 03:20:11 | 显示全部楼层
在这个case中边界条件的判断是以root的左右节点都为null,root == null return 0中的root,即可以是parent(root).left,也可以是parent(root).right。这一步的root是从哪里来的呢?你可以看到minDepth(root.left)实际上是不断地向原函数递归传递左节点,而minDepth(root.right)是在不断地向原函数传递右节点,如果缺少了对另外一边节点是否为null的判断,就会生成伪结果。这也是为何需要在进行最终的root == null return 0之前进行左右节点单独为null情况的判断。
回复 支持 反对

使用道具 举报

st00550055 发表于 2016-9-28 09:18:09 | 显示全部楼层
请问这题为什么node.right and node.left报错
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 12:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表