树与递归模板
树的遍历与 BST 基础操作见 二叉树与平衡树。本文聚焦递归套路的模板化：三要素、前/中/后序的思考方式、LCA 与回溯模板——树题 80% 是递归题。
一、递归三要素
写任何树的递归前，先回答三个问题：
- 终止条件：空节点（
null）返回什么？ - 子问题：对左子树、右子树分别递归能得到什么？
- 合并：当前节点如何把左右子结果合并成自己的返回值？
def solve(root):
if not root: # 1. 终止条件
return base # 空节点返回值
left = solve(root.left)
right = solve(root.right)
return merge(root.val, left, right) # 3. 合并
做题顺序：先写终止条件，再写合并逻辑，最后检查返回值类型是否一致。
二、遍历模板
递归遍历（前/中/后序）
def preorder(root): # 前序：根-左-右
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root): # 中序：左-根-右
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root): # 后序：左-右-根
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
三种遍历的思考角度（面试常考）：
| 遍历 | 核心用途 | 典型题 |
|---|---|---|
| 前序 | 自顶向下传参数、复制树、序列化 | LC 297 序列化 |
| 中序 | BST 有序序列、验证 BST | LC 98、LC 230 |
| 后序 | 自底向上收集信息（深度/最大路径） | LC 104、LC 124、LC 543 |
层序遍历（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
三、递归套路分类
套路 1：自顶向下（传参，答案在过程中记录）
适用于「从根到叶子」的路径类问题——每个节点拿到父节点传来的信息。
def has_path_sum(root, target_sum):
# LC 112：从根到叶子是否存在路径和 = target
if not root:
return False
if not root.left and not root.right:
return root.val == target_sum
return (has_path_sum(root.left, target_sum - root.val) or
has_path_sum(root.right, target_sum - root.val))
套路 2：自底向上（收信息，答案在返回值/闭包中）
适用于「子树统计」类问题——每个节点汇总子树信息再上传。
def max_depth(root):
# LC 104：最大深度
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
def max_path_sum(root):
# LC 124：任意节点间最大路径和（后序 + 闭包）
ans = float('-inf')
def dfs(node):
nonlocal ans
if not node:
return 0
left = max(dfs(node.left), 0) # 负贡献不取
right = max(dfs(node.right), 0)
ans = max(ans, node.val + left + right) # 经过该节点的路径
return node.val + max(left, right) # 只能向单边走
dfs(root)
return ans
判断口诀：「要往下的信息」→ 自顶向下；「要往上的信息」→ 自底向上。
四、BST 操作模板
BST 性质：左 < 根 < 右，中序遍历即有序序列。
查找 / 插入 / 删除（LC 450）
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
验证 BST（LC 98，中序或区间约束）
def is_valid_bst(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]:
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
BST 题三板斧：中序遍历看有序、递归区间约束 (low, high)、把 BST 变有序数组再处理（LC 230 第 K 小）。
五、LCA 模板
最近公共祖先（LC 236）：两个节点在树上的最低公共祖先。
递归模板（自底向上收集 p/q 是否在子树）
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # 左右各含一个，当前即 LCA
return left or right
复杂度：O(n) 时间，O(h) 空间。
变体：
- BST 版（LC 235）：利用大小关系剪枝，比普通版更快。
- 多次查询：先预处理深度 + 倍增（
up[node][k]），单次查询 O(log n)。
六、回溯模板（递归的另一种形态）
回溯 = 递归 + 撤销选择，用于排列/组合/子集（LC 46/78/90）。
def backtrack(nums):
result, path = [], []
def dfs(start):
result.append(path[:]) # 子集：每个前缀都是一个答案
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1) # 组合/子集：i+1 不回头
path.pop() # 撤销选择
dfs(0)
return result
def permute(nums):
# 全排列（LC 46）：每个位置选一个未用过的数
result, path = [], []
used = [False] * len(nums)
def dfs():
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
dfs()
path.pop()
used[i] = False
dfs()
return result
回溯三步：选（append）→ 递归 → 撤销（pop）。去重时先排序，再跳过与前一元素相同且未使用的分支（LC 90/47）。
七、经典题速查表
| 题号 | 题目 | 套路 | 难度 |
|---|---|---|---|
| LeetCode 104 | 二叉树的最大深度 | 自底向上 | Easy |
| LeetCode 112 | 路径总和 | 自顶向下传参 | Easy |
| LeetCode 98 | 验证二叉搜索树 | 中序/区间约束 | Medium |
| LeetCode 230 | BST 第 K 小元素 | 中序 | Medium |
| LeetCode 236 | 二叉树的最近公共祖先 | 后序递归 | Medium |
| LeetCode 124 | 二叉树中的最大路径和 | 后序 + 闭包 | Hard |
| LeetCode 543 | 二叉树的直径 | 后序 + 闭包 | Easy |
| LeetCode 297 | 二叉树的序列化 | 前序/层序 | Hard |
| LeetCode 46/78 | 全排列 / 子集 | 回溯 | Medium |
八、常见问题
Q: 递归的空间复杂度？
递归栈深度 = 树高 h，最坏 O(n)（链状），平衡树 O(log n)。面试被问复杂度要主动提递归栈。
Q: 递归改成迭代怎么写？
前序用栈；中序用「先压左再弹中再转右」；后序用双栈/标记法；层序用队列。面试先用递归保正确，有余力再补迭代。
Q: 回溯和 DFS 的区别？
回溯是 DFS 的一种——它多了一个「撤销选择」，用于枚举所有解（排列/组合），而不是只找一条路径。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。