leetcode110. 平衡二叉树
【摘要】 给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 / \ 9 20 / &nb...
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
思路:左子树是平衡的(返回值不是-1),右子树是平衡的(返回值不是-1),深度差小于2,返回深度。
否则返回-1(告诉父自己不是平衡的)。
-
/**
-
* Definition for a binary tree node.
-
* public class TreeNode {
-
* int val;
-
* TreeNode left;
-
* TreeNode right;
-
* TreeNode(int x) { val = x; }
-
* }
-
*/
-
class Solution {
-
public boolean isBalanced(TreeNode root) {
-
return depth(root) != -1;
-
}
-
private int depth(TreeNode root) {
-
if (root == null) return 0;
-
int left = depth(root.left);
-
if(left == -1) return -1;
-
int right = depth(root.right);
-
if(right == -1) return -1;
-
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/103563910
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)