平衡二叉树
# 📃 题目描述
题目链接:110. 平衡二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
# 🔔 解题思路
平衡二叉树的左右子数高度差不能超过 1,直接调用一波求二叉树最大深度的那段代码,求出左右子数的高度,然后做个比较就行
class Solution {
private boolean res = true;
public boolean isBalanced(TreeNode root) {
getHeight(root);
return res;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int leftHight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHight - rightHeight) > 1) {
res = false;
}
return Math.max(leftHight, rightHeight) + 1;
}
}
二刷的时候我又写了一个比较容易理解的版本:
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return true;
}
// 1. 判断以 root 为根节点的树是否平衡
int left = getHeight(root.left);
int right = getHeight(root.right);
if (Math.abs(left - right) > 1) {
return false;
}
// 2. 递归判断分别 以 root.left 和 root.right 为根节点的子树是否平衡
return isBalanced(root.left) & isBalanced(root.right);
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
else if (root.left == null && root.right == null) {
return 1;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}
可以看到,求高度这段代码我们不动,具体思路分两步走:
- 判断以 root 为根节点的树是否平衡:分别求出 root 的左右子树的高度,如果高度不满足平衡二叉树的定义,直接返回 false
- 判断完了以 root 为根节点的树是否平衡,我们还需要递归判断分别 以root.left 和 root.right 为根节点的树是否平衡
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10