二叉树类的题目，本质几乎从来不在"树"上，而在两件事上：你按什么顺序碰节点，以及在决定父节点要做什么之前，你已经从子节点拿到了什么信息。把这两件事想透，前序、中序、后序、层序四种遍历，递归与迭代两种写法，从两种遍历序列还原一棵树，乃至最大深度、验证 BST 这类经典题，都能收敛到同一套配方上。这篇文章就是把这套配方从头讲到尾。

为了让正文里的图、代码、推理对得上，全文使用同一棵示例树：

它的前序是 [3, 9, 20, 15, 7]，中序是 [9, 3, 15, 20, 7]，后序是 [9, 15, 7, 20, 3]，层序是 [[3], [9, 20], [15, 7]]。后面几乎每一张图都会回到这棵树，看着它读会顺很多。

系列导航

📚 LeetCode 算法精讲系列（共 10 篇）：

哈希表 —— 两数之和、最长连续序列、字母异位词分组
双指针 —— 对撞、快慢、滑动窗口
链表操作 —— 反转、环检测、合并
滑动窗口 —— 定长与变长窗口
二分查找 —— 边界、上下界、对答案二分
二叉树遍历与构造 —— 当前文章
动态规划入门 —— 一维/二维 DP、状态转移
回溯算法 —— 排列、组合、剪枝
贪心算法 —— 区间调度、跳跃游戏
栈与队列 —— 括号匹配、单调栈

二叉树基础

一棵二叉树就这点术语

二叉树是一种树结构，每个节点最多有两个子节点，并且左右子节点是有序的——左右不能随便交换。空树也算二叉树，这个边界看似没意义，但正是它让所有递归定义能干净地收尾。

只有三个名词在题目里反复出现：

根（root）：唯一一个没有父节点的节点。
内部节点（internal node）：至少有一个子节点的节点。
叶子（leaf）：没有子节点的节点。

再加上两个用来描述节点位置的数字：

深度（depth）：从根走到这个节点要经过的边数。根的深度是 0。
高度（height）：从这个节点向下走到任一叶子的最长路径的边数。叶子的高度是 0，整棵树的高度就是根的高度。

把这五个词记牢，本文以及绝大多数二叉树题就有了共同语言。图 1 把它们直接标在示例树上：

最简单的 Python 表示就是一个节点带值、带左右两个指针：

1
2
3
4
5
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

数据结构的全部就这几行，剩下所有内容都是关于"如何走它"。

几种带名字的特殊形状

题目偶尔会用形状作约束，认出来往往能换一个更好的解法。

满二叉树：每个节点要么有 0 个、要么有 2 个子节点，永远不会只有一个。表达式树常见这种形状。
完全二叉树：除最后一层外每层都填满，最后一层从左到右依次填充。堆就是用这种形状存的，也因此可以塞进一维数组里。
平衡二叉树：对任意节点，左右子树高度差不超过 1。AVL、红黑树就是靠维护这一性质把操作压在 $O(\log n)$。
二叉搜索树（BST）：对任意节点，左子树里所有值都严格小于它，右子树里所有值都严格大于它。后面验证 BST 时会直接用到这条性质。

DFS：一个配方，三种顺序

任何深度优先遍历在每个节点上都做三件事——访问当前节点、递归左子树、递归右子树——区别只在三件事的先后。这个先后顺序就是遍历的名字：

顺序	三步排列	在示例树上的访问序列
前序	根 → 左 → 右	`[3, 9, 20, 15, 7]`
中序	左 → 根 → 右	`[9, 3, 15, 20, 7]`
后序	左 → 右 → 根	`[9, 15, 7, 20, 3]`

图 2 把三种顺序画在同一棵树上，每个节点上的编号就是它的访问步数：

记忆只有一句话：根的位置在哪，遍历的名字就是什么——前序根在前、中序根在中、后序根在后。递归代码几乎是定义的逐字翻译：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def preorder(node, out):
    if not node: return
    out.append(node.val)         # 根
    preorder(node.left, out)     # 左
    preorder(node.right, out)    # 右

def inorder(node, out):
    if not node: return
    inorder(node.left, out)      # 左
    out.append(node.val)         # 根
    inorder(node.right, out)     # 右

def postorder(node, out):
    if not node: return
    postorder(node.left, out)    # 左
    postorder(node.right, out)   # 右
    out.append(node.val)         # 根

具体选哪种顺序，本质上取决于"做决定的时候我需要哪些信息已经准备好"。父节点先于子节点拍板的，用前序：复制树、按层级打印目录、序列化时给子节点之前先写出根。BST 相关、需要有序结果的，用中序：有序输出、验证、找第 $k$ 小。父节点的答案要靠子节点的答案合成的，用后序：删除整棵树、统计子树大小或求和、计算高度。

LeetCode 94 —— 中序遍历：把递归和迭代摆在一起看

中序遍历最值得作为"递归 vs 迭代"的入门题，因为它的迭代版几乎一比一暴露了递归调用栈在背后帮你做了什么。

递归版本 直接照定义写：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from typing import List, Optional

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result: List[int] = []

        def visit(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            visit(node.left)         # 1. 一路向左走到底
            result.append(node.val)  # 2. 然后记录当前节点
            visit(node.right)        # 3. 再处理右子树

        visit(root)
        return result

时间 $O(n)$，每个节点访问一次。空间 $O(h)$（$h$ 是树高），递归栈最深就是树高——平衡树是 $O(\log n)$，退化成链表的"歪树"是 $O(n)$。

迭代版本 的关键是看清递归栈到底干了两件事：一是记下回来的路（祖先链），二是处理完左子树后回到上一层继续往右走。这两件事完全可以用一个显式栈来做：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    result: List[int] = []
    stack: List[TreeNode] = []
    cur = root

    while cur is not None or stack:
        # 阶段一：沿左链一路下探，把祖先们入栈备用。
        while cur is not None:
            stack.append(cur)
            cur = cur.left

        # 阶段二：弹出当前最深的未访问祖先，记录它，
        # 然后跳到它的右子树继续遍历。
        cur = stack.pop()
        result.append(cur.val)
        cur = cur.right

    return result

这两个阶段正对应递归调用的两半：入栈相当于"递归向下一层"，出栈相当于"从一层递归返回"。图 4 把递归调用栈和显式栈一帧一帧地摆在一起，会发现它们做的就是同一件事：

迭代版本最容易踩的两个坑：第一，弹栈之后忘记 cur = cur.right，会把同一个节点反复入栈出栈、死循环；第二，把内层 while 写成 if，每次只走一步，遇到左孙子就漏了——必须把整条左链一次性沉到底，再开始第一次出栈。

前序、后序的迭代写法各一段

前序转迭代最省事。把根入栈，然后循环：弹一个、记一个、把右孩子先入栈、左孩子再入栈（栈是 LIFO，左孩子后进就先出）。

1
2
3
4
5
6
7
8
9
def preorderTraversal(self, root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)  # 先入 → 后出
        if node.left:  stack.append(node.left)   # 后入 → 先出
    return out

后序有一个偷懒的小技巧：把上面的前序模板里左右入栈顺序对调（先左后右），得到的访问序列是"根→右→左"，恰好是后序的逆序。所以最后翻转一下就行：

1
2
3
4
5
6
7
8
9
def postorderTraversal(self, root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:  stack.append(node.left)
        if node.right: stack.append(node.right)
    return out[::-1]

这样就避免了"左右子树到底走完了没"这种需要给每个节点打访问状态标签的繁琐簿记。

BFS：层序遍历

DFS 是能往深就往深，BFS 反过来——先把和根距离为 0 的节点访问完，再访问距离为 1 的，依此类推。配套的数据结构是 FIFO 队列，因为我们希望先入队的节点的孩子也先被访问。

BFS 唯一值得专门讲的技巧是层大小快照：每轮外循环开始时，先把当前队列长度记下来，那（且仅那）些节点属于这一层，循环里入队的孩子都属于下一层。

LeetCode 102 —— 层序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque
from typing import List, Optional

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
        return []

    result: List[List[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        # 先把这一层的边界拍下快照，再开始往里塞下一层的孩子
        level_size = len(queue)
        level: List[int] = []

        for _ in range(level_size):
            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

时间 $O(n)$，空间 $O(w)$，$w$ 是树的最大宽度——完全二叉树的最后一层大约 $n/2$ 个节点，所以最坏空间是 $O(n)$。

层大小快照这个套路是一组兄弟问题的共同骨架：锯齿形遍历（每层翻转方向）、二叉树的右视图（取每层最后一个）、最小深度（找到第一个叶子立即返回）、无权图最短路径全都套用同一个壳子，只换几个细节。

两道暖身的 DFS

下面两题代码都不到十行，但分别是后序和中序两种思路最纯粹的模板。

LeetCode 104 —— 二叉树的最大深度：典型后序

整棵树的最大深度，等于左右子树中较深那棵的深度加 1。这是一个递归定义，几乎可以原样翻译成代码：

1
2
3
4
5
6
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    left = self.maxDepth(root.left)
    right = self.maxDepth(root.right)
    return 1 + max(left, right)

这就是后序：父节点的答案需要先把两个孩子的答案凑齐才能给出。同样的骨架还能解：二叉树的直径、判断平衡（用 -1 当不平衡的哨兵值）、子树元素和——只换中间那个"合成"步骤。

LeetCode 98 —— 验证 BST：中序的另一种用法

很多人第一反应会写 node.left.val < node.val < node.right.val 然后递归，这是错的。它只比较了相邻节点，但 BST 要求是"左子树所有节点 < 当前 < 右子树所有节点"——一个深藏在右子树里的节点完全可能违反对远房祖先的约束。

正确的做法是把"当前子树里所有值必须落在的开区间"作为参数传下去：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    def check(node, low: float, high: float) -> bool:
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return (check(node.left,  low,        node.val) and
                check(node.right, node.val,   high))

    return check(root, float("-inf"), float("inf"))

或者换一个角度：直接做一次中序遍历，确认结果严格递增即可——这正是因为 BST 的中序就是排序结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def isValidBST_inorder(self, root: Optional[TreeNode]) -> bool:
    prev = float("-inf")
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if cur.val <= prev:
            return False
        prev = cur.val
        cur = cur.right
    return True

LeetCode 105 —— 从前序与中序遍历构造二叉树

这是构造类最经典的一道，也是把"每种遍历到底告诉了你什么"讲得最清楚的一道。

两个事实。 前序告诉你每个子树的根是谁（永远是当前那段前序切片的第一个）；中序告诉你，知道根之后，左子树到哪结束、右子树从哪开始（根左边的全是左子树，右边的全是右子树）。

这两条结合起来就足以唯一还原整棵树。图 5 把示例树上的递归画了三层：

朴素写法每次递归都重新扫一遍中序、再切两个数组，时间 $O(n^2)$，空间也很浪费。生产质量的写法用一个哈希表把"值 → 中序索引"先建好，然后在索引上递归：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from typing import List, Optional

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """LeetCode 105。时间 O(n)，空间 O(n)。"""
    inorder_index = {v: i for i, v in enumerate(inorder)}
    pre_iter = iter(range(len(preorder)))  # 每访问一个节点就前进一格

    def build(in_left: int, in_right: int) -> Optional[TreeNode]:
        if in_left > in_right:
            return None

        # 由前序的定义，当前要建的子树的根就是 preorder 里的下一个值。
        root_pre_idx = next(pre_iter)
        root_val = preorder[root_pre_idx]
        root = TreeNode(root_val)

        # 它在中序里的位置，决定了左右子树的中序边界。
        mid = inorder_index[root_val]

        # 必须先建左子树！前序是"根-左-右"，
        # 只有先递归左子树，next(pre_iter) 才会顺次拿到正确的下一个根。
        root.left  = build(in_left, mid - 1)
        root.right = build(mid + 1, in_right)
        return root

    return build(0, len(inorder) - 1)

最容易写错的一处是两个递归调用的顺序。前序��根-左-右，所以左子树的根紧跟在当前根之后，必须先建左子树；如果先建右子树，就会把不属于右子树的前序值当成右子树的根，悄无声息地构造出一棵错的树。

姐妹题"从中序 + 后序构造"几乎一模一样，只有两处变化：根在后序的末尾，并且必须先建右子树（因为后序是左-右-根，从尾向前读就成了根-右-左）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def buildTreePost(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    """LeetCode 106。时间 O(n)，空间 O(n)。"""
    inorder_index = {v: i for i, v in enumerate(inorder)}
    post = postorder
    self._i = len(post) - 1

    def build(in_left: int, in_right: int) -> Optional[TreeNode]:
        if in_left > in_right:
            return None
        root_val = post[self._i]
        self._i -= 1
        root = TreeNode(root_val)
        mid = inorder_index[root_val]
        root.right = build(mid + 1, in_right)  # 先右
        root.left  = build(in_left, mid - 1)
        return root

    return build(0, len(inorder) - 1)

为什么前序 + 中序、后序 + 中序都行，前序 + 后序却不行？因为只有中序能告诉你"左子树到哪结束"。最经典的反例：根 1 只有一个左孩子 2 的树，和根 1 只有一个右孩子 2 的树，前序都是 [1,2]、后序都是 [2,1]，但中序一个是 [2,1]、一个是 [1,2]，正好就是中序在区分它们。

递归还是迭代？

维度	递归	迭代
代码复杂度	低，几乎是定义的复述	高，需要自己维护栈
空间	调用栈 $O(h)$	显式栈 $O(h)$
栈溢出风险	树极深时存在（Python 默认约 1000 层）	无，由你掌控
可读性	通常更直观	通常更杂
性能	相当，常数差距	相当

实战建议：先写递归；只在 (a) 面试官明确要求、(b) 树可能很深、(c) 需要在中途带着复杂状态退出递归这三种情况下才改写迭代。中序遍历的迭代模板特别值得背下来——BST 迭代器、第 $k$ 小、双指针在 BST 上找两数之和，几乎都直接套这个模板。

Q&A

为什么 BST 的中序遍历一定有序？

因为 BST 的不变量保证了"所有左后代都小于当前节点、所有右后代都大于当前节点"，而中序遍历的次序正是"先把所有比我小的输出、然后输出我、再把所有比我大的输出"。对深度做归纳就能证明每个值都按递增顺序被输出。这也正是为什么"用中序"是验证 BST、找第 $k$ 小最自然的思路。

任意两种遍历都能唯一还原一棵树吗？

不是。前序+中序 和 后序+中序 在节点值不重复时都能唯一还原；前序+后序 不能。前面给出的反例：根 1 配单个左孩子 2、根 1 配单个右孩子 2，两棵树的前序后序完全相同。原则是：你需要一种遍历来定根（前序或后序），再需要一种遍历来分左右（只有中序能做这件事）。

节点值有重复怎么办？

有重复时即使是前序+中序也不再唯一：preorder = [1, 1]、inorder = [1, 1] 可以对应两棵不同的树。LeetCode 在题目约束里通常会保证值互不相同来回避这个问题；如果在工程里确实有重复值，应该用节点对象的身份（如 id(node)）而不是值来区分。

Morris 遍历值得学吗？

Morris 遍历通过把每个左子树最右节点的右指针临时指向中序后继，再在回上来时改回去，做到 $O(1)$ 额外空间，时间仍是 $O(n)$。但它会在遍历过程中修改树结构，这意味着不能在并发场景里用，且代码也明显更难推理。面试时知道有这么一种解法可以加分，工程里通常还是显式栈更稳妥——多出来的一点常数因子换来的可维护性几乎总是值得。

为什么层序遍历的时间复杂度是 $O(n)$？

每个节点恰好入队一次、出队一次，所以总队列操作次数是 $2n$。队列在某一时刻的最大长度是 $O(w)$（树的最大宽度），这才是空间复杂度的主导项。

总结

整篇文章可以收敛到两条贯穿性的思想，把它们带进任何一道二叉树题里都用得上：

DFS 是同一个配方——访问、递归左、递归右——四种遍历的区别只在"访问"这一步发生在哪个位置上。 前序在子节点之前定调，后序在子节点之后回总，中序卡在两者中间；层序则把 LIFO 调用栈换成了 FIFO 队列，于是先把距离 $k$ 的所有节点处理完，再去碰距离 $k+1$ 的。
递归和显式栈是同一个算法的两件外衣。 入栈对应"递进一层"，出栈对应"从一层返回"。把这件事想透之后，“把这段递归改成迭代"就不再是一种独立技能，而是一次机械的翻译。

构造类问题（LeetCode 105/106）只是同一配方的应用：前序或后序告诉你根，中序告诉你左右分界，然后递归处理两半。

面试前的核对清单：递归版前/中/后/层序——会；迭代版中序（显式栈模板）——会；用"值→中序索引"哈希表写出 $O(n)$ 的"前序+中序构造”——会；最大深度和验证 BST 这两个小题作为"能讲清楚的代表性例子"——会。这五个模板成肌肉记忆之后，绝大多数二叉树类的 LeetCode 题都能在五分钟内拿下。

LeetCode（六）—— 二叉树遍历与构造