二叉树 解题模板

适用场景

树结构遍历、递归分治、路径查找、构建转换

通用模板

DFS 三种遍历

 
# 前序：根→左→右
 
def preorder(root):
 
    if not root: return
 
    visit(root)
 
    preorder(root.left)
 
    preorder(root.right)
 
# 中序：左→根→右
 
def inorder(root):
 
    if not root: return
 
    inorder(root.left)
 
    visit(root)
 
    inorder(root.right)
 
# 后序：左→右→根
 
def postorder(root):
 
    if not root: return
 
    postorder(root.left)
 
    postorder(root.right)
 
    visit(root)
 

BFS 层序

 
from collections import deque
 
q = deque([root])
 
while q:
 
    for _ in range(len(q)):
 
        node = q.popleft()
 
        if node.left: q.append(node.left)
 
        if node.right: q.append(node.right)
 

BST 二分查找

 
def search(root, val):
 
    while root:
 
        if root.val == val: return root
 
        if val < root.val: root = root.left
 
        else: root = root.right
 
    return None
 

复杂度总结

模式	时间	空间	典型题
DFS 递归	O(n)	O(h)	遍历、路径、LCA
BFS 迭代	O(n)	O(w)	层序、右视图
后序遍历	O(n)	O(h)	最大路径和、打家劫舍III
分治构建	O(n)	O(h)	前序+中序构建树

核心套路

• 后序 + 全局变量：计算子树信息的同时更新答案（直径、最大路径和）

• BST 中序 = 有序数组：第 K 小、验证 BST

• 递归三要素：终止条件、本层逻辑、下层递归

关键要点

• 递归转迭代：需要自己维护栈

• 后序迭代最难：需要记录右子树是否已访问

• Morris 遍历：O(1) 空间遍历

→ 查看该分类题目：LeetCode学习路线图 > 五、二叉树

---

相似题对比

易混题对	关键区别	解法差异
104最大深度 vs 111最小深度	叶子定义不同，最小深度不能直接 min	最小深度要判断叶子节点
98验证BST vs 94中序遍历	验证 vs 遍历	BST验证可转中序检查递增
235BST的LCA vs 236二叉树的LCA	BST有序 vs 普通树	BST可二分，普通树需后序
100相同的树 vs 101对称二叉树	两树比较 vs 镜像比较	isSame(t1,t2) vs isMirror(t1,t2)
105前序+中序构建 vs 106中序+后序构建	前序根在首 vs 后序根在末	逻辑对称
114二叉树展开为链表 vs 297序列化	原地展开 vs 编码表示	展开用前驱连接，序列化用字符串

---

测试用例模板

 
# 边界
 
assert maxDepth(None) == 0                 # 空树
 
root = TreeNode(1)
 
assert maxDepth(root) == 1                 # 单节点
 
# assert maxDepth(root) == 3
 

---

关联题型

关联题型	常见结合方式	典型题目
回溯	DFS + 路径记录	112路径总和, 257二叉树路径
动态规划	树形DP	337打家劫舍III, 124最大路径和
栈	迭代遍历	94中序, 144前序, 145后序