我们之前学过数组的遍历、链表的遍历，这些线性结构的遍历考起来没有什么难度，可以理解为基本技能，一般也不会单独出题。

但是二叉树可不一样了，这一“开叉”，它的遍历难度陡然上了一个台阶。在面试中，二叉树的各种姿势的遍历，是非常容易作为独立命题点来考察的，而且这个考察的频率极高极高。 因此对于有志于在算法面试上求稳的同学，本节涉及的编码内容，你千万不要沉溺在“我看懂了”、“我理解了”、“我知道你说的是啥意思了”这种虚无的成就感中——假的，都是假的，只有自己写出来的代码才是真的！

理解只是记忆的前提，只吹理解不记忆，不如回家去种地：）。

这里我对大家的要求就是“在理解的基础上记忆”。如果你真的暂时理解不了，背也要先给你自己背下来，然后带着对正确思路的记忆，重新去看解析部分里的图文（尤其是图）、反复去理解，这么整下来你不可能学不会。 面试时见到二叉树的遍历，你不能再去想太多——没有那么多时间给你现场推理，这么熟悉的题目你没必要现场推理，你要做的是默写！默写啊！老哥们！！（捶胸顿足）

二叉树的遍历——命题思路解读

⚡ 30 秒速记

• 四种遍历：先序（根左右）、中序（左根右）、后序（左右根）、层序（一层一层）
• 先/中/后说的是「根什么时候处理」，左子树永远先于右子树
• 怎么选看数据依赖：父要用孩子的结果 → 后序；BST 要有序输出 → 中序；要最浅一层 → 层序
• 前三种是深度优先，递归或手写栈；层序用队列
• 时间都是 O(n)；深搜空间 O(h)，层序空间 O(w)，完全二叉树最后一层能到 n/2

二叉树遍历就是按固定规则把每个结点走一遍，先、中、后序的区别只在根结点什么时候处理。 比如 A 下面挂 B、C，先序是 A B C，中序 B A C，后序 B C A，左边永远先于右边。实际选哪种我看数据往哪个方向流：父结点要等孩子算完（求树高、汇总子树大小）就用后序，二叉搜索树要从小到大吐出来就用中序，要找离根最近的结点就用层序。复杂度上四种都是 O(n)，但层序的队列会装下一整层，宽树上比深搜吃内存。

遍历方式应从数据依赖反推。若父结点结果依赖左右子树，就要先得到孩子再处理父亲，对应后序；若利用二叉搜索树“左小、根中、右大”的约束输出有序值，则用中序。层序让距离根相同的结点连续出现，适合最短层数、逐层聚合和宽度问题。

四种遍历都至少访问每个结点一次，时间为 O(n)。深度优先保存当前根到叶的路径，辅助空间 O(h)；广度优先保存当前层的候选结点，最坏 O(w)。完全二叉树最后一层宽度接近 n/2，所以层序空间不能简单说成 O(log n)。

以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历。按照顺序规则的不同，遍历方式有以下四种：

• 先序遍历
• 中序遍历
• 后序遍历
• 层次遍历

按照实现方式的不同，遍历方式又可以分为以下两种：

• 递归遍历（先、中、后序遍历）
• 迭代遍历（层次遍历）

层次遍历的考察相对比较孤立，我们会把它放在后续的真题归纳解读环节来讲。这里我们重点要看的是先、中、后序遍历三兄弟——由于同时纠结了二叉树和“递归”两个大热命题点，又不属于“偏难怪”之流，遍历三兄弟一直是前端算法面试官们的心头好，考察热度经久不衰。