判断一个二叉树是否是平衡树

平衡二叉树_牛客网

https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

平衡二叉树:平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
题目:输入一棵二叉树,判断该二叉树是否是平衡二叉树。
思路:利用求深度的方法,依次遍历左右子树,用他们的深度相减,结果大于1的,返回-1;否则返回树的深度
代码:
public boolean IsBalanced_Solution(TreeNode root) {
if (TreeDepth(root) == -1) {
return false;
}
return true;
}
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = TreeDepth(root.left);
if (left == -1) {
return -1;
}
int right = TreeDepth(root.right);
if (right == -1) {
return -1;
}
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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