Leetcode刷题100天—110.平衡二叉树(AVL树)—day05
【摘要】 前言:作者:神的孩子在歌唱大家好,我叫运智给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。示例 1:输入:root = [3,9,20,null,null,15,7]输出:true示例 2:输入:root = [1,2,2,3,3,null,null,4,4]输出:false示例 3:输入:roo...
前言:
作者:神的孩子在歌唱
大家好,我叫运智
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:true
示例 2:
输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
示例 3:
输入:root = []
输出:true
提示:
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package AVL树;
/*
* 1
* https://leetcode-cn.com/problems/balanced-binary-tree/
*/
public class _110_平衡二叉树 {
public boolean isBalanced(TreeNode root) {
// 如果不是-1就返回true
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
// 通过递归,然后由底向上判断,先获取最后一个左子树的左右子树节点
int leftHeight = height(node.left), rightHeight= height(node.right);
// 因为如果存在一棵子树不平衡,则整个二叉树一定不平衡,我们通过左右子树相减,符合平衡条件是0,-1,1,如果高度差的绝对值大于1,说明不符合平衡,直接返回false
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1)
return -1;
// 选择该节点左右子树中高度最高的加1返回,然后接着向上一个节点判断
return Math.max(leftHeight, rightHeight) + 1;
}
}
本人csdn博客:https://blog.csdn.net/weixin_46654114
转载说明:跟我说明,务必注明来源,附带本人博客连接。
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)