二叉树与平衡树
树是一种层级结构的数据结构，在面试中出现频率极高。从简单的遍历到复杂的平衡树设计，掌握树的各类问题是算法面试的必备技能。
一、二叉树基础
定义与术语
1 ← 根节点（Root）
/ \
2 3 ← 内部节点
/ \ \
4 5 6 ← 叶节点（Leaf）
- 深度（Depth）：从根到该节点的边数。根深度为 0。
- 高度（Height）：从该节点到叶节点的最长边数。叶高度为 0。
- 满二叉树：所有层节点数达到最大值。
- 完全二叉树：除最后一层外满，最后一层左对齐。
节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
二、遍历方法
1. 前序遍历（Preorder: 根-左-右）
# 递归
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# 迭代（栈）
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
2. 中序遍历（Inorder: 左-根-右）
# 递归
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
# 迭代
def inorder_iterative(root):
result, stack = [], []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
关键性质：BST 的中序遍历为有序序列。
3. 后序遍历（Postorder: 左-右-根）
# 递归
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
# 迭代（双栈法）
def postorder_iterative(root):
if not root:
return []
stack1, stack2 = [root], []
while stack1:
node = stack1.pop()
stack2.append(node.val)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
return stack2[::-1]
4. 层序遍历（BFS）
from collections import deque
def level_order(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
三、二叉搜索树（BST）
性质
- 左子树所有节点 < 根
- 右子树所有节点 > 根
- 左右子树也是 BST
查找与插入
class BST:
def search(self, root, val):
if not root or root.val == val:
return root
if val < root.val:
return self.search(root.left, val)
return self.search(root.right, val)
def insert(self, root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insert(root.left, val)
else:
root.right = self.insert(root.right, val)
return root
删除（最复杂）
三种情况：
- 叶节点：直接删除
- 一个子节点：用子节点替代
- 两个子节点：用右子树最小值（或左子树最大值）替代
def delete(self, root, val):
if not root:
return None
if val < root.val:
root.left = self.delete(root.left, val)
elif val > root.val:
root.right = self.delete(root.right, val)
else:
if not root.left:
return root.right
if not root.right:
return root.left
min_node = self.find_min(root.right)
root.val = min_node.val
root.right = self.delete(root.right, min_node.val)
return root
def find_min(self, root):
while root.left:
root = root.left
return root
复杂度：查找/插入/删除平均 O(log n)，最坏 O(n)（退化为链表）。
四、平衡二叉树
1. AVL 树
严格平衡：左右子树高度差 ≤ 1。
平衡因子 = 左子树高度 - 右子树高度，只能为 -1, 0, 1。
不平衡的四种情况：
- LL（左左）：右旋
- RR（右右）：左旋
- LR（左右）：先左旋后右旋
- RL（右左）：先右旋后左旋
def rotate_right(self, y):
x = y.left
T3 = x.right
x.right = y
y.left = T3
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
2. 红黑树
近似平衡，通过五条颜色规则保证最长路径不超过最短路径的 2 倍。
应用场景：Java TreeMap/TreeSet、Linux 内核、C++ map（部分实现）。
对比 AVL：
- AVL 查询更快（更严格平衡）
- 红黑树插入/删除更快（旋转次数少）
五、Trie 树（字典树）
用于高效存储和检索字符串集合。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find_node(prefix) is not None
def _find_node(self, word):
node = self.root
for char in word:
if char not in node.children:
return None
node = node.children[char]
return node
应用：自动补全、拼写检查、IP 路由最长前缀匹配。
六、高频面试题
| 题号 | 题目 | 考点 | 难度 |
|---|---|---|---|
| LeetCode 104 | 二叉树的最大深度 | 递归 / DFS | Easy |
| LeetCode 226 | 翻转二叉树 | 递归 | Easy |
| LeetCode 98 | 验证二叉搜索树 | 中序有序 / 递归 | Medium |
| LeetCode 230 | BST第K小元素 | 中序遍历 | Medium |
| LeetCode 124 | 二叉树中的最大路径和 | 后序递归 | Hard |
| LeetCode 208 | 实现 Trie（前缀树） | Trie 结构 | Medium |
| LeetCode 297 | 二叉树的序列化与反序列化 | 设计题 | Hard |
七、面试常见问题
Q: 递归 vs 迭代的遍历怎么选？
- 面试写递归更简洁，但需说出空间复杂度 O(h)
- 迭代（ Morris 遍历）可将空间降到 O(1)，高级加分项
Q: 如何不用递归实现后序遍历？
双栈法：一个栈做前序的根-右-左，结果再反转即得左-右-根。
Q: 为什么工程实现常用红黑树而不是 AVL？
红黑树插入删除的旋转操作更少（最多 3 次旋转），在频繁修改的场景下性能更好。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。