平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- 判断每个节点左右子树的高度差是否小于 1，可从上往下判断，也可从下往上判断
- 从上往下，如果根节点满足高度差小于 1，继续遍历左右子树节点是否符合条件。
# 节点 1：高度差小于 1，左右子树不一定平衡
1
/ \
2 2
/ \
3 3
/ \
4 4
- 从下往上，判断节点左右子树是否为平衡树，通过两者的高度再判断节点是否为平衡树
# 节点 1：左右子树平衡，高度差不一定小于 1
1
/ \
2 2
/ \
3 3
/ \
4 4
- 标签：
从上往下、递归 - 时间复杂度：如果树是平衡二叉树，节点被重复遍历的次数与所在层数对应。
- 空间复杂度：函数调用栈的高度。函数调用栈的高度等于树的高度。如果树完全倾斜，树有 n 个节点，高度为 n。最差空间复杂度为 O(n)
# Python3
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if root == None:
return True
if abs(self.height(root.left) - self.height(root.right)) > 1:
return False
else:
return self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self, root: TreeNode) -> int:
if root == None:
return 0
if root.left == None and root.right == None:
return 1
else:
return 1 + max(self.height(root.left),self.height(root.right))// Java
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
} else {
return isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
} else {
return 1 + Math.max(height(root.left),height(root.right));
}
}
}- 同时返回子树是否平衡和子树的高度。也可只返回高度差？
- 标签：
从下往上 - 时间复杂度：O(n)，n 为节点的数量，每个节点只会遍历一次
- 空间复杂度：O(n)，函数调用栈的高度等于树的高度。如果树完全倾斜，树有 n 个节点，高度为 n。最差空间复杂度为 O(n)
# Python3
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
return self.isBalancedHelper(root)[0]
def isBalancedHelper(self, root: TreeNode) -> (bool,int):
if root == None:
return True,0
if root.left == None and root.right == None:
return True,1
leftIsBalanced,leftHeight = self.isBalancedHelper(root.left)
if not leftIsBalanced:
return False,0
rightIsBalanced,rightHeight = self.isBalancedHelper(root.right)
if not rightIsBalanced:
return False,0
return abs(leftHeight - rightHeight) <= 1,1 + max(leftHeight,rightHeight)// Java，使用 List 存放 isBalanced 和 height
class Solution {
public boolean isBalanced(TreeNode root) {
return (Boolean)isBalancedHelper(root).get(0);
}
public List<Object> isBalancedHelper(TreeNode root) {
if (root == null) {
return new ArrayList<Object>(){{add(true);add(0);}};
}
if (root.left == null && root.right == null) {
return new ArrayList<Object>(){{add(true);add(1);}};
}
List<Object> leftList = isBalancedHelper(root.left);
boolean leftIsBalanced = (Boolean)leftList.get(0);
int leftHeight = (Integer)leftList.get(1);
if (!leftIsBalanced) {
return new ArrayList<Object>(){{add(false);add(0);}};
}
List<Object> rightList = isBalancedHelper(root.right);
boolean rightIsBalanced = (Boolean)rightList.get(0);
int rightHeight = (Integer)rightList.get(1);
if (!rightIsBalanced) {
return new ArrayList<Object>(){{add(false);add(0);}};
}
return new ArrayList<Object>(){{
add(Math.abs(leftHeight - rightHeight) <= 1);
add(1 + Math.max(leftHeight,rightHeight));
}};
}
}// Java，使用对象
class Solution {
public boolean isBalanced(TreeNode root) {
return isBalancedHelper(root).isBalanced;
}
public TreeInfo isBalancedHelper(TreeNode root) {
if (root == null) {
return new TreeInfo(true, 0);
}
if (root.left == null && root.right == null) {
return new TreeInfo(true, 1);
}
TreeInfo treeInfoLeft = isBalancedHelper(root.left);
boolean leftIsBalanced = treeInfoLeft.isBalanced;
int leftHeight = treeInfoLeft.height;
if (!leftIsBalanced) {
return new TreeInfo(false, 0);
}
TreeInfo treeInfoRight = isBalancedHelper(root.right);
boolean rightIsBalanced = treeInfoRight.isBalanced;
int rightHeight = treeInfoRight.height;
if (!rightIsBalanced) {
return new TreeInfo(false, 0);
}
boolean isBalanced = Math.abs(leftHeight - rightHeight) <= 1;
int height = 1 + Math.max(leftHeight,rightHeight);
return new TreeInfo(isBalanced, height);
}
}
final class TreeInfo {
final boolean isBalanced;
final int height;
public TreeInfo(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
} 3
/ \
9 20
/ \
15 7
[3,9,20,null,null,15,7]
1
/ \
2 2
/ \
3 3
/ \
4 4
[1,2,2,3,3,null,null,4,4]
1
/
2
[1,2]
1
/ \
2 2
/ \
3 3
/ \
4 4
[1,2,2,3,null,null,3,4,null,null,4]
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if root == None:
return True
return slef.isBalanced(left) and self.isBalanced(root.right)
1 3 2 20
return abs(height(left,1) - height(right,1)) <= 1
def judge(self, root: TreeNode) -> bool:
if root.left == None and root.right == None:
return true
return judge(root.left)[0] and judge(root.left)[0]
if abs(self.height(root.left) - self.height(root.right)) <= 1:
return true
return False
return judge(root.left) and judge(root.left)
def height(root: TreeNode) -> int:
if root.left == None and root.right == None:
return 1
else:
return 1+max(height(root.left),height(root.right))- 如果左子树是平衡树，返回高度，如果不是，结束递归；如果右子树是平衡树，返回高度，如果不是，结束递归。
- 从上往下比较
- 1 是
- 2 不是
- 从下往上比较，
- 1 有左右子树，往下
- 4 是，左右子树高度为 0
- 3 是，左右子树高度为 1 和 0
- 2 不是，左右子树高度为 2 和 0，结束