041. 编写一个函数，检查一个二叉树是否是平衡二叉树
在 Python 中，可以通过递归方法检查一个二叉树是否是平衡二叉树。平衡二叉树的定义是：对于树中的每个节点，其左右子树的高度差不超过 1。
示例代码
class TreeNode:
"""
定义二叉树的节点类。
"""
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_balanced(root):
"""
检查二叉树是否是平衡二叉树。
参数:
root (TreeNode): 二叉树的根节点。
返回:
bool: 如果二叉树是平衡二叉树，返回 True；否则返回 False。
"""
def check_height(node):
"""
递归检查节点的高度，并判断是否平衡。
参数:
node (TreeNode): 当前节点。
返回:
int: 如果子树平衡，返回子树的高度；否则返回 -1。
"""
if not node:
return 0 # 空节点的高度为 0
left_height = check_height(node.left)
if left_height == -1:
return -1 # 左子树不平衡
right_height = check_height(node.right)
if right_height == -1:
return -1 # 右子树不平衡
if abs(left_height - right_height) > 1:
return -1 # 当前节点不平衡
return max(left_height, right_height) + 1 # 返回当前节点的高度
return check_height(root) != -1
# 测试代码
# 创建一个平衡二叉树
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print("平衡二叉树检查结果：", is_balanced(root)) # 输出：True
# 创建一个不平衡二叉树
# 1
# /
# 2
# /
# 3
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
print("不平衡二叉树检查结果：", is_balanced(root)) # 输出：False
代码解释
定义二叉树节点类：定义了一个 TreeNode 类，表示二叉树的节点。每个节点包含一个值 value 和两个指向左右子节点的指针 left 和 right。
定义主函数：定义了一个名为 is_balanced 的函数，用于检查二叉树是否是平衡二叉树。
递归检查高度：
-
定义了一个辅助函数
check_height，用于递归检查每个节点的高度，并判断是否平衡。 -
如果当前节点为空，返回高度 0。
-
递归检查左子树和右子树的高度。
-
如果左子树或右子树不平衡，返回 -1。
-
如果当前节点的左右子树高度差超过 1，返回 -1。
-
否则，返回当前节点的高度（左右子树高度的最大值加 1）。
返回结果：如果 check_height(root) 返回的不是 -1，说明二叉树是平衡的，返回 True；否则返回 False。
测试结果
运行上述代码后，输出如下：
平衡二叉树检查结果： True
不平衡二叉树检查结果： False
注意事项
递归方法：
-
递归方法通过检查每个节点的左右子树高度差来判断是否平衡。
-
如果某个节点的左右子树高度差超过 1，直接返回 -1，避免不必要的计算。
效率：该方法的时间复杂度为 O(n)，其中 n 是二叉树的节点数。每个节点只会被访问一次。
适用场景：适用于需要判断二叉树是否平衡的场景，例如在 AVL 树或红黑树的实现中。
视频讲解
BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)