二叉树遍历：前序、中序、后序与层序

学完树的基本概念之后，二叉树里最先必须掌握的一件事，就是遍历。因为二叉树本身只是节点和左右孩子之间的组织关系，真正要做查找、统计、打印、构造、序列化时，第一步几乎总是“怎么把整棵树有顺序地访问一遍”。而不同的访问顺序，决定了我们看到这棵树的方式也不同。

这也是为什么二叉树遍历会成为数据结构里的基础中的基础。前序、中序、后序、层序这四类遍历，不只是几种访问顺序而已，它们对应着四种非常不同的思考方式：

  • 是先处理根，还是先处理子树；
  • 是自顶向下，还是自底向上理解结构；
  • 是更偏递归定义，还是更偏层次推进。

后面你学 BST、表达式树、序列化、层次搜索、树形 DP，都会不断回到这几个遍历方式上。所以这一篇一定要真正理解“为什么这么遍历”，而不是只把代码模板背下来。

一、为什么遍历是树结构的核心操作

数组和链表的遍历通常比较自然：

  • 数组按下标从前到后扫；
  • 链表沿指针一路往后走。

但树不一样。树不是一条线，而是一个分支结构。于是“访问所有节点”这件事本身就需要先定义顺序。

例如同样一棵二叉树：

  • 可以先看根；
  • 也可以先看左子树；
  • 还可以一层一层地看。

所以遍历本质上是在回答：

我准备按照什么规则，把树中的每个节点恰好访问一次？

这个“规则”不同，得到的节点序列就不同，适用场景也会不同。

二、为什么二叉树的遍历特别适合递归理解

因为二叉树本身就具有非常强的递归结构：

  • 一棵二叉树由根节点、左子树、右子树组成；
  • 左子树和右子树本身又各自是一棵二叉树。

所以很多遍历定义几乎可以直接写成递归：

  • 先处理根，再递归左子树和右子树；
  • 或先递归左子树，再处理根，再递归右子树；
  • 或先递归两边子树，最后处理根。

也正因为这个特点，二叉树遍历是把递归真正用顺的一块关键训练场。

三、什么是前序遍历

前序遍历的顺序是：

  1. 访问根节点；
  2. 前序遍历左子树；
  3. 前序遍历右子树。

通常记作：

1
根 -> 左 -> 右

前序遍历最直观的特点是：

  • 总是先看到当前根；
  • 再一步步向下展开整个结构。

所以前序遍历很适合那些“需要先处理当前节点，再递归处理子问题”的场景。

典型应用包括：

  • 树的复制；
  • 序列化时记录结构起点；
  • 表达式树的前缀表示；
  • 输出带层级结构的遍历结果。

四、什么是中序遍历

中序遍历的顺序是：

  1. 中序遍历左子树；
  2. 访问根节点；
  3. 中序遍历右子树。

通常记作：

1
左 -> 根 -> 右

中序遍历在二叉树里非常特殊，因为它把根夹在左右子树中间。对于普通二叉树来说，这只是某种访问顺序；但对于二叉搜索树来说，中序遍历会得到一个有序序列。

这也是为什么后面学 BST 时，中序遍历会变得极其重要。

五、什么是后序遍历

后序遍历的顺序是：

  1. 后序遍历左子树；
  2. 后序遍历右子树；
  3. 访问根节点。

通常记作：

1
左 -> 右 -> 根

后序遍历的核心特点是：

  • 总是先处理完子问题；
  • 最后再回到当前根。

所以它很适合：

  • 计算树高；
  • 统计节点信息；
  • 释放整棵树；
  • 表达式树的后缀表示；
  • 一切需要“先拿到子树结果，再计算当前节点结果”的问题。

从递归角度看，后序遍历和“自底向上”思维非常接近。

六、什么是层序遍历

层序遍历和前三种很不一样。它不是按递归定义来，而是按层次来访问：

  1. 先访问根节点；
  2. 再访问第二层所有节点；
  3. 然后访问第三层所有节点；
  4. 依此类推，从上到下、从左到右逐层访问。

层序遍历的关键工具通常是队列。

基本思路是：

  • 先把根节点入队；
  • 每次取出队头节点并访问；
  • 再把它的左右孩子按顺序入队；
  • 重复直到队列为空。

所以层序遍历实际上是树结构里一个非常典型的 BFS。

七、前中后序为什么常被放在一起比较

因为这三者的结构非常相似，区别只在“访问根节点”放在什么位置。

1. 前序

根最先访问，适合自顶向下展开问题。

2. 中序

根夹在左右中间，适合二叉搜索树这类有序结构。

3. 后序

根最后访问，适合自底向上汇总问题。

所以真正学遍历，不是把三套代码死记，而是看清：

根节点在递归流程中的位置不同，问题视角就不同。

八、递归写法为什么如此自然

以前序遍历为例，伪代码几乎就是定义本身：

1
2
3
4
5
6
def preorder(root):
    if root is None:
        return
    visit(root)
    preorder(root.left)
    preorder(root.right)

中序和后序也只是 visit(root) 的位置不同。

这就是树遍历里最值得抓住的一个认识：

好的递归代码，本质上是在直接翻译结构定义。

所以如果你总觉得树遍历代码像模板，很可能是因为还没有真正把“结构定义”和“递归顺序”对上。

九、非递归遍历为什么也重要

虽然递归写法很自然，但在真实开发和面试里，非递归遍历也非常重要。

原因主要有两个：

1. 递归本质依赖调用栈

如果树很深，递归可能带来栈空间问题。

2. 非递归更能暴露你对遍历过程的真实理解

因为你必须显式维护状态，而不是把过程交给系统调用栈。

通常：

  • 前序和中序遍历常用显式栈实现；
  • 后序遍历稍复杂，常借助两个栈或访问标记；
  • 层序遍历则天然用队列。

所以“会写递归版本”只是第一步，“看懂并写出非递归版本”才说明你真的理解了遍历过程。

十、为什么中序遍历在 BST 里特别重要

这是后面会不断用到的结论。

对于二叉搜索树，满足：

  • 左子树所有节点值小于根；
  • 右子树所有节点值大于根。

于是中序遍历顺序：

1
左 -> 根 -> 右

恰好会把节点按从小到大访问出来。

也就是说：

中序遍历是把 BST 的结构性有序，转成序列有序的桥梁。

这一点极其重要。

十一、层序遍历最常用在哪里

层序遍历并不只是“多一种遍历方式”，它很适合处理和“层”有关的问题。

例如：

  • 求树的最小深度；
  • 按层打印节点；
  • 判断完全二叉树；
  • 查看每层节点数；
  • 宽度相关问题。

因为它天然就是一层层推进，所以凡是题目里强调“最近一层”“下一层”“最短步数”的味道时，都很容易想到层序遍历。

十二、遍历顺序和问题类型怎么对应

可以先建立这样一个直觉：

1. 前序遍历

适合“先处理当前节点，再处理子树”的问题。

2. 中序遍历

适合“左边处理完再看当前，再看右边”的有序结构问题。

3. 后序遍历

适合“必须先知道左右子树结果，才能处理当前节点”的问题。

4. 层序遍历

适合“按层推进、按波次处理”的问题。

真正理解这一层之后，遍历就不再是四种孤立模板，而是四种问题视角。

十三、学习遍历时最容易踩的坑

1. 只记住访问顺序，不理解适用场景

这样一到题目里就只会机械套模板。

2. 把前中后序写混

本质上就是没有真正抓住“根节点访问时机”的区别。

3. 不理解空节点的边界处理

树遍历里 root is None 这种终止条件非常重要。

4. 只会递归，不会非递归

这说明对调用栈和显式状态维护理解还不够。

5. 不会把遍历和实际问题联系起来

比如看不出“求高度用后序”“按层处理用层序”这种对应关系。

总结

二叉树遍历的重要性，不只是因为它经常考，而是因为它几乎定义了你如何与树结构交互。真正值得先建立起来的，是这些核心认识：

  • 遍历是在树这种非线性结构中，为“访问全部节点”定义访问顺序；
  • 前序、中序、后序的本质区别，在于根节点放在递归流程中的位置不同；
  • 层序遍历则不是递归型顺序，而是借助队列做逐层推进；
  • 前中后序更适合表达结构递归，层序更适合表达按层扩展；
  • 中序遍历在 BST 中尤其重要，因为它能得到有序序列；
  • 真正学会遍历，不是背代码模板，而是知道什么问题该用哪种顺序去看树。

把这一篇理解透之后，后面再去学 BST、AVL、红黑树和树上各种计算问题时，你会越来越意识到：很多树题表面不同，核心往往只是“选对遍历顺序”。

参考资源：