查看: 1675| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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/

上一篇:LC里的 List<List<Integer>>
下一篇:不用recursion遍历Binary Tree
🔗
invisibili 2015-6-15 06:41:57 | 只看该作者
全局:
比如说有个node 只有右子树 这个node就不是leaf 但是没有那两个if就会把这个node当作leaf然后返回1 结果就错了

评分

参与人数 1大米 +3 收起 理由
Artemis + 3 多谢~!:)

查看全部评分

回复

使用道具 举报

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

         1
      /     \
    /        \
  2         Null

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

评分

参与人数 1大米 +3 收起 理由
Artemis + 3 谢谢!懂啦~

查看全部评分

回复

使用道具 举报

🔗
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大米 +3 收起 理由
Artemis + 3 Thanks! It is very helpful~

查看全部评分

回复

使用道具 举报

全局:
在这个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报错
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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