【平衡二叉树的判定】在数据结构中，平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，其特点是每个节点的左右子树高度差不超过1。这种特性保证了树的查找、插入和删除操作的时间复杂度为O(log n)，从而提高了效率。
判断一棵二叉树是否为平衡二叉树，是算法设计中的常见问题。以下是对该问题的总结与分析。
一、判定方法总结
| 判定方法 | 描述 | 时间复杂度 | 空间复杂度 |
| 后序遍历法 | 递归地检查每个节点的左右子树高度差，并返回是否平衡 | O(n) | O(h)（h为树的高度） |
| 前序遍历法 | 每个节点都检查左右子树是否平衡，可能导致重复计算 | O(n²) | O(h) |
| 自底向上法 | 通过一次遍历同时计算高度并判断是否平衡，效率更高 | O(n) | O(h) |
二、关键概念说明
- 高度（Height）：从根节点到最远叶子节点的边数。
- 平衡因子（Balance Factor）：左子树高度减去右子树高度。
- 平衡二叉树定义：所有节点的平衡因子绝对值 ≤ 1。
三、实现思路对比
| 方法 | 实现逻辑 | 是否推荐 |
| 后序遍历 | 从下往上判断，避免重复计算 | ✅ 推荐 |
| 前序遍历 | 每次都要重新计算高度，效率低 | ❌ 不推荐 |
| 自底向上 | 结合后序遍历思想，优化递归过程 | ✅ 推荐 |
四、代码示例（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):
def check_height(node):
if not node:
return 0
left = check_height(node.left)
right = check_height(node.right)
if abs(left - right) > 1 or left == -1 or right == -1:
return -1
return max(left, right) + 1
return check_height(root) != -1
```
五、结论
平衡二叉树的判定是二叉树相关算法中的重要知识点。通过合理的遍历方式和递归设计，可以高效地完成判断。推荐使用自底向上的后序遍历方法，既保证了时间效率，又避免了不必要的重复计算。掌握这一方法有助于提升对二叉树结构的理解与应用能力。
