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

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

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

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

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

⚡ 30 秒速记

• 遍历要按确定顺序访问每个结点一次；二叉树常见先序、中序、后序和层序
• 先、中、后描述根结点相对左右子树的访问时机，三者默认都保持左子树先于右子树
• 深度优先可用递归或显式栈，层序使用队列；选顺序取决于结果对父子结点的依赖
• 复制常用先序，搜索树有序输出用中序，删除或汇总子树用后序，最浅层问题常用层序
• 四者时间都是 O(n)；深搜辅助空间 O(h)，层序队列最坏保存树的最大宽度 O(w)

二叉树遍历就是按确定顺序访问每个结点一次，常见方式是先序、中序、后序和层序。 前三种本质上区别在于根结点相对左右子树何时处理，可用递归或显式栈；层序则用队列逐层访问。选择顺序要看数据依赖，例如搜索树有序输出适合中序，父结点依赖子树结果时适合后序。它们时间都是 O(n)，深度优先空间为 O(h)，层序最坏为树的最大宽度 O(w)。

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

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

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

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

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

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

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