【平衡二叉树的判定】在数据结构中，平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树（BST），其特点是每个节点的左右子树高度差不超过1。这种特性使得树的查找、插入和删除操作的时间复杂度保持在O(log n)，从而保证了较高的效率。
判断一棵二叉树是否为平衡二叉树，是算法设计中的一个常见问题。以下是对该问题的总结与分析。
一、判断方法概述
要判断一棵二叉树是否为平衡二叉树，通常需要对每个节点进行以下两步检查：
1. 计算左右子树的高度差：若差值超过1，则不是平衡二叉树。
2. 递归判断左右子树是否也为平衡二叉树：只有当所有节点都满足条件时，整棵树才是平衡的。
常见的实现方式有两种：
- 自顶向下：从根节点开始，递归地检查每个节点的左右子树是否平衡。
- 自底向上：从叶子节点开始，向上返回子树的高度，并在过程中判断是否平衡。
二、关键点对比
| 项目 | 自顶向下法 | 自底向上法 |
| 实现方式 | 递归检查每个节点的左右子树 | 递归返回子树高度，同时判断是否平衡 |
| 时间复杂度 | O(n²)（最坏情况） | O(n)（平均情况） |
| 空间复杂度 | O(h)（h为树的高度） | O(h)（h为树的高度） |
| 是否重复计算高度 | 是（每个节点都要重新计算） | 否（高度在递归中传递） |
| 适用场景 | 小规模或简单结构的树 | 大规模或复杂结构的树 |
三、代码示例（Python）
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
自顶向下法
def is_balanced(root):
if not root:
return True
left_height = height(root.left)
right_height = height(root.right)
if abs(left_height - right_height) > 1:
return False
return is_balanced(root.left) and is_balanced(root.right)
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
自底向上法
def is_balanced_bottom_up(root):
def helper(node):
if not node:
return (True, 0)
left_balanced, left_height = helper(node.left)
right_balanced, right_height = helper(node.right)
if not left_balanced or not right_balanced:
return (False, 0)
if abs(left_height - right_height) > 1:
return (False, 0)
return (True, 1 + max(left_height, right_height))
balanced, _ = helper(root)
return balanced
```
四、结论
平衡二叉树的判定是一个典型的递归问题，核心在于正确计算子树高度并判断其是否符合平衡条件。虽然自顶向下的方法实现较为直观，但其时间复杂度较高；而自底向上的方法通过优化高度计算，提高了效率，更适合实际应用。
在实际开发中，建议优先使用自底向上的方法，以提升性能和可维护性。