找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 850|回复: 4
收起左侧

[基础刷题题目讨论] 110. Balanced Binary Tree

[复制链接]

6

主题

0

精华

58

积分

资深会员

Rank: 2

积分
58
发表于 1-9-2017 06:08 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
关于这道题,之前在Cracking Coding Interview 上看到过解答,但是那上面的解答不被Leetcode 接受,我test了好几次,不知道问题在哪里,所以贴出来想和大家讨论一下,也希望大牛给指点一下。

1. Method from Cracking the Coding Interview
[code]public class Solution {
   
    public boolean isBalanced(TreeNode root) {
        return (maxDepth(root) - minDepth(root) <=1);
    }
   
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
    }
   
    public int minDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        return 1+Math.min(minDepth(root.left), minDepth(root.right));
    }
   
}[/code]Leetcode 的报错信息,附在图片中

2. Accepted Method(这是常用解法,为了对比,也贴出来了)
[code]public class Solution {
   
    public boolean isBalanced(TreeNode root) {
        return (maxDepth(root) != -1);
    }
   
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        if(left == -1 || right == -1 || Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left, right)+1;
    }
   
}[/code]


另外,两题对于balanced binary tree 的描述略有不同,但我觉得意思好像是一样的,如下:
Leetcode:a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Cracking the coding Interview: a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

应该说两题主要思路差不多,都是通过recursive function找到depth for root,然后进行相应处理,但主要的判断式是根据各自定义来的,所以有所不同,难道还是两个定义的差异造成的问题吗?求解~非常感谢~




0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 1-9-2017 06:09 PM 来自美国米群网手机版 | 显示全部楼层
感谢zhangyuwinnie分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 1-12-2017 02:53 PM | 显示全部楼层
感谢zhangyuwinnie分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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