目录
题目
-
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
自顶向下
- 首先，对当前节点进行处理，计算左孩子的高度，右孩子的高度，两者高度差若大于1返回False，否则返回True，递归判断左子树、右子树
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
#根
a,b=0,0
#如果有左孩子a+1，一直往下走到没有左孩子的地方
while root.left is not None :
a+=1
root=root.left
#如果有右孩子b+1，一直往下走到没有右孩子的地方
while root.right is not None :
b+=1
root=root.right
#如果a-b或者b-a的值大于1，返回F，否则返回T
if a-b >1 or b-a >1:
return False
else :
return True
#递归左
return self.isBalanced(root.left)
#递归右
return self.isBalanced(root.right)
- 只能判断每个节点的左右子树的高度差是否小于等于1，但并未考虑整棵树的平衡性。比如[1,2,3,4,5,6,null,8]，上述代码求的左子树高为a=3,右子树高为b=1,而实际右子树的高度为2，问题出在计算b的时候只往右走，实际的高度是左右里面较大的一个才对。
自顶向下正解
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
# 计算左子树的高度
left_height = self.get_height(root.left)
# 计算右子树的高度
right_height = self.get_height(root.right)
# 判断当前节点的左右子树高度差是否大于1
if left_height-right_height >1 or right_height-left_height >1:
return False
#######这个地方不能写返回True，返回了后面就不会对左右子树进行判断了######
# else :
# return True
#递归左
return self.isBalanced(root.left) and self.isBalanced(root.right)
#####左右子树的递归不可以分开写，会导致左子树返回了，右子树没执行######
# return self.isBalanced(root.left)
# #递归右
# return self.isBalanced(root.right)
def get_height(self, node):#求树的高度
if node is None:
return 0
#树的高度为：左子树高度和右子树高度较大的一个并+1
return max(self.get_height(node.left), self.get_height(node.right)) + 1
自底向上（优）
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def recur(root):
# 递归函数，计算每个节点的高度并判断子树是否平衡
if not root:
return 0 # 空节点的高度为0
# 递归计算左子树的高度
left = recur(root.left)
if left == -1:
return -1 # 左子树不平衡，直接返回-1
# 递归计算右子树的高度
right = recur(root.right)
if right == -1:
return -1 # 右子树不平衡，直接返回-1
# 判断当前节点的左右子树高度差是否大于1
if abs(left - right) > 1:
return -1 # 左右子树高度差大于1，返回-1表示不平衡
# 返回左右子树中较大的高度加1作为当前子树的高度
return max(left, right) + 1
# 调用递归函数判断整棵树是否平衡
return recur(root) != -1