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

二叉树的题目，核心其实不在“树”本身，而在于两点：访问节点的顺序，以及在处理父节点之前，从子节点那里得到了什么信息。只要厘清这两点，前序、中序、后序、层序遍历的区别，递归与迭代的实现方式，乃至由两种遍历序列重建二叉树，甚至求最大深度、验证 BST 等经典题目，都能纳入同一套方法论框架。这篇文章的目的，就是带你彻底掌握这套方法。

为了方便讲解，全文统一使用一棵示例树，所有图解和代码都基于它：

这棵树的前序遍历是 [3, 9, 20, 15, 7]，中序遍历是 [9, 3, 15, 20, 7]，后序遍历是 [9, 15, 7, 20, 3]，层序遍历是 [[3], [9, 20], [15, 7]]。后面的内容会反复用到这棵树，建议随时对照着看，理解起来会更顺畅。

二叉树基础#

二叉树的核心术语#

二叉树是一种每个节点最多有两个子节点的树结构，且左右子节点是有顺序的——左就是左，右就是右，不能随便调换。空树也被视为二叉树。这一定义看似简单，却是保证所有递归操作能正确终止的关键。

题目里反复出现的名词其实就三个：

根节点（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

数据结构本身就这么几行代码，剩下的内容全是怎么遍历它。

几种有名字的特殊树形#

有些题目会用特定的树形作为约束条件，能认出来的话，往往能找到更优的解法。

满二叉树：每个节点要么没有子节点，要么有两个子节点，绝不会只有一个。这种结构在表达式树中很常见。
完全二叉树：除了最后一层，其他层都填满，且最后一层从左到右依次排列。堆就是用这种结构存储的，因此可以直接用数组实现。
平衡二叉树：对任意节点，左右子树的高度差不超过 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 的有序性，那就用中序——比如输出排序结果、验证 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，每次只走一步，遇到左孙子就漏掉了——必须先沿着左子节点一路向下，将整条左链节点全部入栈，再开始首次出栈。

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

前序遍历改成迭代很简单。先把根节点压栈，然后进入循环：每次弹出一个节点记录值，接着先压右孩子、再压左孩子（因为栈是后进先出，左孩子后压就能先处理）。

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 的定义要求的是“左子树所有节点 < 当前节点 < 右子树所有节点”。右子树深处的一个节点完全可能违反与远房祖先的关系。

正确的做法是引入一个动态区间 (low, high)，表示当前子树中所有节点值必须落在的范围：

 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 上两数之和等问题基本都能直接套用这个模板。

常见问题#

为什么 BST 的中序遍历结果一定是有序的？#

BST 的核心性质决定了：所有左子树的节点值都小于当前节点，所有右子树的节点值都大于当前节点。而中序遍历的顺序是“先左、再根、最后右”，正好符合从小到大的输出逻辑。通过归纳法可以证明，每个节点都会按照递增顺序被访问。这也是为什么验证 BST 或查找第 $$k$$ 小元素时，中序遍历是最自然的选择。

任意两种遍历组合能唯一确定一棵树吗？#

不一定。前序+中序 和 后序+中序 在节点值不重复的情况下可以唯一还原树，但 前序+后序 不行。举个反例：一棵树是根节点 1 带一个左孩子 2，另一棵树是根节点 1 带一个右孩子 2，它们的前序和后序完全相同，但结构完全不同。原因很简单：你需要一种遍历来确定根（前序或后序），还需要另一种遍历来区分左右子树（只有中序能做到这一点）。

如果节点值有重复会怎样？#

如果允许重复值，即使是前序+中序也无法保证唯一性。比如 preorder = [1, 1] 和 inorder = [1, 1] 可以对应两棵不同的树。LeetCode 的题目通常会假设节点值互不相同来避免这个问题；在实际工程中，如果有重复值，可以通过节点对象的身份（例如 id(node)）而不是值本身来区分。

Morris 遍历值得学吗？#

Morris 遍历通过临时修改树结构实现 $$O(1)$$ 的额外空间复杂度，具体做法是把左子树的最右节点指向当前节点的中序后继，处理完后再恢复原状。时间复杂度仍然是 $$O(n)$$ ，但它会在遍历过程中修改树结构，这在并发场景下可能引发问题，代码也更难理解。面试时提到 Morris 遍历是个加分项，但在工程实践中，显式栈的实现虽然多了一点常数开销，但换来的是更高的可维护性和安全性，通常是更好的选择。

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

层序遍历的核心操作是入队和出队，每个节点恰好入队一次、出队一次，总共的操作次数是 $$2n$$ 。真正影响空间复杂度的是队列的瞬时最大长度，也就是树的最大宽度 $$O(w)$$ 。对于完全二叉树来说，最宽的一层可能包含约 $$n/2$$ 个节点，因此空间复杂度的上界是 $$O(n)$$ 。

总结#

这篇文章的核心可以归结为两个关键点，掌握了它们，几乎所有的二叉树问题都能迎刃而解：

DFS 遵循一个通用模板：访问当前节点、递归遍历左子树、递归遍历右子树；三种（非四种） DFS 遍历方式的区别仅在于‘访问’操作发生的时机。 前序是在处理子节点之前先定调；后序是等子节点都处理完后再收尾；中序则是卡在左右子树之间；层序则把 LIFO 的递归栈换成 FIFO 队列，按照距离根节点的层数一层层处理。
递归和显式栈其实是同一个算法的不同实现形式。 入栈相当于进入下一层递归，出栈相当于从递归返回。一旦理解了这一点，“把递归改成迭代”就不再是额外的技能，而是简单的代码转换。

构造类问题（比如 LeetCode 105 和 106）也是这个思路的应用：前序或后序用来确定根节点，中序用来划分左右子树，然后递归处理两边。

面试前的检查清单：

递归版前序、中序、后序、层序——熟练掌握；
迭代版中序（显式栈模板）——熟练掌握；
用“值→中序索引”哈希表实现 $$O(n)$$ 的“前序+中序构造”——熟练掌握；
最大深度和验证 BST 作为小而精的例题——能讲清楚思路；

把这些模板练到肌肉记忆的程度，绝大多数二叉树相关的 LeetCode 题基本都能在五分钟内搞定。

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

二叉树基础#

二叉树的核心术语#

几种有名字的特殊树形#

DFS：一个配方，三种顺序#

LeetCode 94 —— 中序遍历：递归与迭代的对比#

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

BFS：层序遍历#

LeetCode 102 —— 层序遍历#

两道暖身的 DFS#

LeetCode 104 —— 二叉树的最大深度：后序遍历的典型应用#

LeetCode 98 —— 验证 BST：中序遍历的妙用#

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

递归还是迭代？#

常见问题#

为什么 BST 的中序遍历结果一定是有序的？#

任意两种遍历组合能唯一确定一棵树吗？#

如果节点值有重复会怎样？#

Morris 遍历值得学吗？#

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

总结#

LeetCode 算法模式 10 篇

读有所得？

二叉树基础#

二叉树的核心术语#

几种有名字的特殊树形#

DFS：一个配方，三种顺序#

LeetCode 94 —— 中序遍历：递归与迭代的对比#

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

BFS：层序遍历#

LeetCode 102 —— 层序遍历#

两道暖身的 DFS#

LeetCode 104 —— 二叉树的最大深度：后序遍历的典型应用#

LeetCode 98 —— 验证 BST：中序遍历的妙用#

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

递归还是迭代？#

常见问题#

为什么 BST 的中序遍历结果一定是有序的？#

任意两种遍历组合能唯一确定一棵树吗？#

如果节点值有重复会怎样？#

Morris 遍历值得学吗？#

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

总结#

LeetCode 算法模式 10 篇

读有所得？

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