想象你第一次走进祖传的老宅：正堂坐着族长，左厢房住着大房一脉，右厢房住着二房一脉，每个房间又通向更深的套间。若要把整座宅子的族人登记成一份名单，你会怎么走？是先拍正堂再钻左厢，还是把左厢所有人登记完再回来登记族长，又或者直接一层一层扫过去？这正是二叉树遍历要回答的问题——如何设计一条“走访路线”，让每个房间恰好被访问一次。前序、中序、后序、层序四种路线，加上递归、迭代、Morris 等不同走法，构成了树上一切操作的底盘：搜索、排序、序列化、表达式求值，全都从这里出发。本文就用这座老宅作比，带你从头把每条路线走一遍，再看它们在真实工程里如何派上用场。

岗位关联

职业价值：遍历是所有树算法（AVL、红黑树、表达式树、序列化）的公共底盘，吃透它等于拿到了手撕树类面试题的“入场券”，也是理解海量数据存储与检索的必备直觉。

目录
  1. 可视化演示
  2. 遍历概念
  3. 前序遍历
  4. 中序遍历
  5. 后序遍历
  6. 层序遍历
  7. Morris遍历
  8. 序列与重建
  9. 复杂度实战
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

二叉树遍历包括前序、中序、后序和层序四种方式，每种遍历有不同的应用场景和实现方式。本文讲解四种遍历的递归与迭代... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

前序中序后序：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

遍历概念

老宅的构造有个特点：每个房间都像一座微缩版的老宅。正堂（根）连着左厢房和右厢房，而左厢房内部的套间，又由它自己的“正堂”和更小的左右厢房构成。计算机里把这结构叫二叉树——一个节点最多伸出两个分支，左边叫左孩子，右边叫右孩子，每个孩子又各自是一棵独立的树。这就是“递归定义”：大树里套着小树，小树里套着更小的树。

遍历的本质，就是沿着这些房间的通道，把每个节点都“拜访”恰好一次，且不重复、不遗漏。难点在于：通道有分叉，你必须约定一个固定的顺序。就好比族谱登记，你可以先记族长再往下走，也可以把所有晚辈记完最后才记族长——路线不同，最后形成的名单顺序完全不一样。这四种经典路线，就是前序、中序、后序与层序。

正因为“左子树和右子树依然是树”，我们才能把一栋大宅的登记任务，拆成“登记正堂 + 登记左厢 + 登记右厢”三个小任务——这扇门一推开，后面所有的递归实现和分治思想就都顺理成章了。

Tree(T)={ root(T), Tree(T.left), Tree(T.right) }\text{Tree}(T) = \{\, \text{root}(T),\ \text{Tree}(T.\text{left}),\ \text{Tree}(T.\text{right}) \,\}
这行式子说明：一棵树 T 由三部分组成——它的根节点、它的左子树、它的右子树，而左右子树本身又是同款结构。这正是所有遍历算法能“递归地”解决问题的基础。
  1. root(T)当前这棵树的根节点，相当于族谱里坐在正堂的那位族长，是整个支系的起点。
    root(T)\text{root}(T)
  2. Tree(T.left)根的左子树，即左厢房这一整支血脉。它内部依然是一棵完整的树，有自己的根和左右分支。
    Tree(T.left)\text{Tree}(T.\text{left})
  3. Tree(T.right)根的右子树，即右厢房那支血脉，同样自成一棵树。
    Tree(T.right)\text{Tree}(T.\text{right})

前序遍历

假设老宅要编一本《全族名录》，规矩是：先记录正堂的主人，再进左厢房，最后进右厢房；每进一个套间，也同样先记录套间主人，再往它的左边走，最后走右边。这条“每到一处先记自己”的路线，就是前序遍历，严格顺序为 根 → 左 → 右。

实现上，递归写法最直观：一个函数“visit(node)“先收集当前节点的值，然后调用自己处理 node.left，再调用自己处理 node.right——三个动作的顺序就是代码的书写顺序。如果不想用递归（防止栈溢出），可以用一个显式的栈：先把根压栈，循环弹出节点并记录，然后把右孩子压栈、左孩子压栈，因为栈是后进先出，左孩子后压就会先弹出，正好模拟”先左后右”。

前序最典型的应用是目录树打印：命令行里执行 tree 命令时，系统从根目录出发，每进入一个文件夹就先打印它自己，再依次递归打印子文件夹——这正是前序遍历。同理，复制一棵树时，也必须先创建根节点，再挂载左右子树，天然就是前序节奏。前序还常用于序列化，因为它保证根在子树前面，方便后续重建。

Pre(T)=visit(root(T))→Pre(T.left)→Pre(T.right)\text{Pre}(T) = \text{visit}\left(\text{root}(T)\right) \to \text{Pre}\left(T.\text{left}\right) \to \text{Pre}\left(T.\text{right}\right)
前序遍历的递归定义：访问根节点之后，整棵左子树先被完整遍历完，再轮到整棵右子树。
  1. visit(root(T))立刻把正堂族长“登记在案”，这是整条路线上第一个被记录的人。
    visit(root(T))\text{visit}\left(\text{root}(T)\right)
  2. Pre(T.left)登记完族长，转身进左厢房，把那一整支按同样的“根→左→右”规则全部走完，不走完绝不回头。
    Pre(T.left)\text{Pre}\left(T.\text{left}\right)
  3. Pre(T.right)左支系全部搞定了，才踏进右厢房，处理剩余那一支。
    Pre(T.right)\text{Pre}\left(T.\text{right}\right)

中序遍历

换一种规矩：登记时要求“左支的人排前面，族长排中间，右支的人排后面”。于是你必须先把左厢房所有人都登记完，回到正堂记录族长，最后再去右厢房。这条“左 → 根 → 右”的路线，就是中序遍历。在家族谱系里，如果左支是晚辈右支是长辈，中序名单就是按辈分排列的；而在计算机的二叉搜索树（BST）里，左孩子永远比根小、右孩子永远比根大，因此中序遍历一棵 BST 得到的一定是升序序列——这是“排序”和“第 k 小元素”问题的核心武器。

递归实现不过是在前序代码上调整一行顺序：先递归左边、再访问自己、最后递归右边。迭代版本则需要更精心：用栈沿着左链一路压进去（一直往左走到头），弹出一个节点记录它，然后转到该节点的右孩子，重复这套动作。这个过程可以理解为“先把左边一整条走廊的房门都推开但不进门，走到尽头后开始边回头边记录”。

中序遍历的工程价值，很大程度绑定在二叉搜索树上：校验一棵树是否是合法的 BST、把 BST 转成有序数组、找出第 k 小的元素，全都是中序的活儿。对应到老宅比喻：如果你想要一份“按长幼顺序排好”的全族名单，中序就是唯一正确的走访路线。

In(T)=In(T.left)→visit(root(T))→In(T.right)\text{In}(T) = \text{In}\left(T.\text{left}\right) \to \text{visit}\left(\text{root}(T)\right) \to \text{In}\left(T.\text{right}\right)
中序定义：左子树整个遍历完，根节点才被访问，最后遍历右子树。
  1. In(T.left)先把左厢房整支登记完毕，此刻族长还在名单外等着。
    In(T.left)\text{In}\left(T.\text{left}\right)
  2. visit(root(T))回到正堂，把族长写入名单正中间，保证左右两支以他为界。
    visit(root(T))\text{visit}\left(\text{root}(T)\right)
  3. In(T.right)最后踏入右厢房，登记剩余的族人，让名单“左小右大”地排开。
    In(T.right)\text{In}\left(T.\text{right}\right)

后序遍历

老宅要清点全族家产，规矩反过来：必须先统计完左厢房所有房间的财产，再统计右厢房，最后才把两边数字汇总到正堂族长那里。这条“左 → 右 → 根”的路线，就是后序遍历。它天然适合一切“先知道孩子才能算出父亲”的任务——比如表达式树求值：(3 + 5) × (2 - 1) 这棵树的根是 ×，要先算出左右子树 3+5=8、2-1=1，最后才能算 8×1=8，顺序强制为后序。

递归实现最简单：先递归左、再递归右、最后访问自己。迭代实现常用双栈法：第一个栈负责模拟“根→右→左”的前序变形压栈，弹出的节点压入第二个栈；由于第二个栈后进先出，最终弹出来的顺序恰好被反转成“左→右→根”。另一类做法是单栈加 pre 指针记录上次访问节点，当发现当前节点的左右孩子都已被访问时才访问它。

后序在系统里最常见的另一个场景是释放树的节点：删除一棵以 root 为根的树时，必须先删光左右子树再删 root，否则先删根就找不到孩子了。它和中序、前序构成了“三种深度优先路线”的完整拼图，三者差别只有一行代码的顺序，但含义截然不同。

Post(T)=Post(T.left)→Post(T.right)→visit(root(T))\text{Post}(T) = \text{Post}\left(T.\text{left}\right) \to \text{Post}\left(T.\text{right}\right) \to \text{visit}\left(\text{root}(T)\right)
后序定义：两棵子树全部搞定，根节点最后才被访问，是“自底向上”汇总信息的典型顺序。
  1. Post(T.left)深入左厢房，把所有子孙的财产逐间清点完毕，数字沉淀在左支的统计里。
    Post(T.left)\text{Post}\left(T.\text{left}\right)
  2. Post(T.right)右厢房也完成同样的清点，两个支系的明细都已就绪。
    Post(T.right)\text{Post}\left(T.\text{right}\right)
  3. visit(root(T))最后回到正堂，把左右两边的结果合并到族长名下，整棵树的汇总才真正完成。
    visit(root(T))\text{visit}\left(\text{root}(T)\right)

层序遍历

前三种路线都是“一头扎进走廊深处”的深度优先，而层序遍历是另外一派的思路：像人口普查那样，按排点名——先登记第一排的正堂和左右厢房，再登记第二排所有套间，一排一排扫过去，绝不越过当前排。这种“逐层推进”的方式就是广度优先搜索（BFS），核心数据结构是队列（FIFO）。

具体流程：把根节点放入队列，然后循环——从队首弹出一个节点并登记它，再把它的左孩子、右孩子依次排到队尾。因为队列先进先出，所以上一层的节点总比下一层的节点先被弹出，天然形成“一层接一层”的效果。如果要逐层分行输出，技巧是记录每轮开始时队列的长度 size，连续弹出 size 个节点即为完整一层，然后再进入下一轮。

层序遍历的应用很广：求二叉树的最小深度（第一次遇到叶子就返回）、判断一棵树是否完全二叉树、按层打印树形结构、在树状网络中找最短路径，都建立在 BFS 之上。它和前三种“深挖到底”的路线相比，更像一个稳扎稳打、逐排扫楼的普查员。

LevelOrder(T):q=[ T ];while q≠∅: v=dequeue(q); visit(v); enqueue(v.left,v.right)\text{LevelOrder}(T):\quad q = [\,T\,];\quad \text{while } q \neq \varnothing:\ v = \text{dequeue}(q);\ \text{visit}(v);\ \text{enqueue}(v.\text{left}, v.\text{right})
层序的伪代码：队列初始只装根节点；每弹出一个节点就登记它，并把它的两个孩子排到队尾，直到队列空。
  1. q = [T]在登记簿边放一张“待访名单”，先把正堂族长写上去。
    q=[ T ]q = [\,T\,]
  2. v = dequeue(q)从名单最前面撕下一张，取出的就是要当前登记的那个房间。
    dequeue(q)\text{dequeue}(q)
  3. visit(v)登记这个房间的主人。
    visit(v)\text{visit}(v)
  4. enqueue(v.left, v.right)把它的左孩子和右孩子按顺序写到名单末尾，保证它们在这一排全部登记完之后才被轮到。
    enqueue(v.left,v.right)\text{enqueue}(v.\text{left}, v.\text{right})

Morris遍历

前三种遍历的递归实现要消耗系统递归栈，迭代实现要手动维护一个栈，空间复杂度最坏都是 O(h)。那有没有可能既不用递归栈也不用显式栈，只靠常数个指针就把树走完？Morris 遍历给出了答案：它利用二叉树里大量闲置的空指针——“叶子节点的右孩子本来就空着”——临时把它改造成指向某个祖先的线索，走完后再把树恢复原样。好比普查员不随身带纸笔，而是每走到一个门前，用粉笔在门框上画个箭头指向“下一步该去哪”，登记完再擦掉，全程只靠一支粉笔。

以中序 Morris 为例：从根出发，若当前节点没有左孩子，直接访问它并向右走；若有左孩子，先找到左子树中“最靠右”的节点（也就是中序意义上的前驱），如果前驱的右指针为空，就把右指针临时指向当前节点（建立线索），然后当前节点向左走；如果前驱的右指针已经指向自己（说明左子树刚走完，这是回来收尾的），就清除线索、访问当前节点、向右走。走完全程，所有临时线索都被擦除，树恢复原貌。

Morris 适用于对空间极其敏感的场景，比如嵌入式设备、内存极小的固件环境，或处理超大二叉树时不想让递归栈爆掉。日常业务开发中，递归和显式栈更易读易懂；但 Morris 这种“借空指针当草稿纸、用完即擦”的巧思，正是面试官最爱问的思维题——它逼迫你跳出“必须用容器记住路径”的思维定式。

TMorris(n)=O(n),SMorris(n)=O(1)T_{\text{Morris}}(n) = O(n), \qquad S_{\text{Morris}}(n) = O(1)
Morris 遍历的复杂度：总时间仍与节点数成线性关系（每条边最多被额外走两趟：设线索一趟、清除线索一趟），而空间却压到了常数级 O(1)。
  1. T(n) = O(n)摊还来看，每个节点至多被访问常数次，找前驱的过程虽然单次可能爬上 O(h)，但所有找前驱的开销加起来仍是 O(n)，所以总时间线性。
    TMorris(n)=O(n)T_{\text{Morris}}(n) = O(n)
  2. S(n) = O(1)全程只用 cur 和 pred 两个指针，既不申请节点栈，也不依赖递归调用栈，空间恒定。
    SMorris(n)=O(1)S_{\text{Morris}}(n) = O(1)

序列与重建

如果族谱在战火中遗失了一部分，只剩两份名单：一份前序、一份中序，能不能把整棵老宅的族谱恢复出来？能。秘密在于前序的第一个节点永远是全树的根（族长）；拿着这个根到中序名单里一查，它左边那些名字就是左支系全体成员，右边那些就是右支系全体成员。于是原问题被劈成两个更小的子问题：用前序里的左段 + 中序里的左段重建左子树，用右段 + 右段重建右子树——递归下去，整棵树跃然纸上。

在 LeetCode 第 105 题“从前序与中序遍历序列构造二叉树”中，朴素实现每次用 inorder.index(root_val) 找根的位置，最坏 O(n²)；优化做法是先用一张哈希表记录中序里每个值的位置，查找变成 O(1)，总时间降到 O(n)。需要留意的是，节点值必须互异，否则无法区分同名族人；另外，单靠前序+后序通常无法唯一重建，因为无法确定根节点的两个孩子划分边界，只有满二叉树（每个节点要么有两个孩子要么是叶子）时才唯一。

序列化与反序列化同样依赖遍历：工程上常把二叉树按前序遍历写成带特殊空标记的字符串（如 1,2,4,#,#,5,#,#,3,...），反序列化时再按前序顺序重建——正因为前序“先根后孩子”，只要读到一个值就能立刻创建节点并递归挂接孩子，非常自然。这就是“从名单还原族谱”在数据库缓存、RPC 消息、分布式存储中的真实上演。

T(n)=T(k)+T(n−k−1)+O(n)T(n) = T(k) + T(n - k - 1) + O(n)
重建的时间复杂度递归式：k 是左子树大小，n−k−1 是右子树大小；每层递归都要 O(n) 时间在中序中定位根，总复杂度 O(n)。
  1. T(k)重建左子树的开销，左支系有 k 个人需要还原。
    T(k)T(k)
  2. T(n−k−1)重建右子树的开销，右支系有 n−k−1 个人。
    T(n−k−1)T(n - k - 1)
  3. O(n)每次在中序序列里找到根的位置、切分左右子序列的代价，用哈希表优化后就是 O(n) 级的总开销。
    O(n)O(n)

复杂度实战

把四种路线摊开对比，时间上所有遍历都是 O(n)——每个节点恰好被访问一次，没有哪种路线在时间上“更快”；真正拉开差距的是空间。递归实现会消耗调用栈，深度等于树高 h，最坏退化成链时是 O(n)；显式栈迭代同样是 O(h)。层序的队列空间取决于树的最大宽度 w，满二叉树的最后一层能有约 n/2 个节点，所以也是 O(n) 量级。Morris 则是唯一空间恒定 O(1) 的路线，代价是代码更绕、常数更大。

工程选型的口诀是“看你的目的是什么”：复制或序列化树，用前序，先下手为强；BST 排序、校验有序性，用中序；表达式求值、删除整棵树，用后序，孩子算完父亲才有材料；找最短层数、逐层报表，用层序；空间极度受限、树巨大且只读，才考虑 Morris。选对路线，遍历这栋老宅的每一步都心中有数。

T所有遍历(n)=O(n),S递归(n)=O(h),S层序(n)=O(w),SMorris(n)=O(1)T_{\text{所有遍历}}(n) = O(n), \quad S_{\text{递归}}(n) = O(h), \quad S_{\text{层序}}(n) = O(w), \quad S_{\text{Morris}}(n) = O(1)
一句话记忆：时间是“线性”，空间看“深度或宽度”——深度优先吃树高，广度优先吃宽度，Morris 什么都不吃。
  1. T(n) = O(n)无论前中后层、无论递归迭代，每个节点恰被访问一次。
    T(n)=O(n)T(n) = O(n)
  2. S(n) = O(h)递归和显式栈的空间都由树高 h 决定，斜树的最坏情况 h = n。
    S递归(n)=O(h)S_{\text{递归}}(n) = O(h)
  3. S(n) = O(w)层序队列同时容纳一层节点，w 为树的最大宽度。
    S层序(n)=O(w)S_{\text{层序}}(n) = O(w)
  4. S(n) = O(1)Morris 只借几个指针，空间恒为常数。
    SMorris(n)=O(1)S_{\text{Morris}}(n) = O(1)

AI 应用场景

表达式树求值（编译器与计算器引擎）

阶段：模型推理 / 规则引擎评估

解决的问题：AI 系统中处理公式、规则表达式时，传统做法是反复扫描字符串，效率低且容易出错。将表达式解析成一棵二叉树，用后序遍历自底向上求值，每个操作符都等左右孩子算完再合并，天然正确且一次遍历完成。

具体案例：某智能风控系统需要评估大量“IF 条件 THEN 动作”规则，规则引擎把每条规则编译成表达式树，后序遍历批量求值，单条规则的评估耗时从毫秒级降到微秒级。

目录树遍历与文件统计分析

阶段：数据预处理 / 特征工程

解决的问题：训练大模型前需要梳理海量数据集目录结构，传统 shell 脚本面对百万级文件时难以统计各子目录分布。用前序遍历或层序遍历扫描目录树，按需输出层级结构或统计每层文件数量，为数据采样策略提供依据。

具体案例：某 NLP 团队的语料库包含 40 万个文件，工程师用前序遍历生成目录清单、层序遍历按目录深度统计 token 总量，据此决定分层采样比例，把数据清洗时间缩短 70%。

树结构的序列化与反序列化

阶段：模型存储 / 分布式缓存

解决的问题：AI 系统中的索引结构、决策树模型需要持久化到磁盘或传输到其他节点，传统做法是自定义格式且难以校验。用前序遍历 + 空标记把二叉树压成一个字符串，读取时再按前序重建，信息零丢失。

具体案例：某推荐系统的决策树冷启动时从 Redis 加载序列化字符串，反序列化重建整棵树仅需几毫秒，比逐节点写入快一个数量级，且天然兼容版本迁移。

Python 演示

python93 行
from collections import deque  class TreeNode:    def __init__(self, val, left=None, right=None):        self.val = val        self.left = left        self.right = right  def preorder_traversal(root):    """前序遍历：根 -> 左 -> 右（递归）"""    if not root:        return []    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)  def inorder_traversal(root):    """中序遍历：左 -> 根 -> 右（递归）"""    if not root:        return []    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)  def postorder_traversal(root):    """后序遍历：左 -> 右 -> 根（递归）"""    if not root:        return []    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]  def levelorder_traversal(root):    """层序遍历：BFS 队列实现"""    if not root:        return []    result, q = [], deque([root])    while q:        node = q.popleft()        result.append(node.val)        if node.left:            q.append(node.left)        if node.right:            q.append(node.right)    return result  def morris_inorder(root):    """Morris 中序遍历：O(1) 空间"""    result, cur = [], root    while cur:        if not cur.left:            result.append(cur.val)            cur = cur.right        else:            pred = cur.left            while pred.right and pred.right is not cur:                pred = pred.right            if not pred.right:                pred.right = cur                cur = cur.left            else:                pred.right = None                result.append(cur.val)                cur = cur.right    return result  def build_tree(preorder, inorder):    """由前序 + 中序重建二叉树"""    if not preorder:        return None    root_val = preorder[0]    idx = inorder.index(root_val)    left = build_tree(preorder[1:idx + 1], inorder[:idx])    right = build_tree(preorder[idx + 1:], inorder[idx + 1:])    return TreeNode(root_val, left, right)  if __name__ == "__main__":    # 构造二叉树:     1    #               /   \    #              2     3    #             / \   / \    #            4   5 6   7    tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)),                    TreeNode(3, TreeNode(6), TreeNode(7)))    print("前序:", preorder_traversal(tree))    print("中序:", inorder_traversal(tree))    print("后序:", postorder_traversal(tree))    print("层序:", levelorder_traversal(tree))    print("Morris中序:", morris_inorder(tree))    rebuilt = build_tree([1, 2, 4, 5, 3, 6, 7], [4, 2, 5, 1, 6, 3, 7])    print("重建后中序:", inorder_traversal(rebuilt))
目的：一棵满二叉树同时跑四种遍历 + Morris 中序 + 前中序重建，打印全部结果，验证各算法输出一致性。
  1. class TreeNode:定义树节点，含值、左孩子、右孩子三个字段，是整栋“老宅”的最小房间单元。
  2. preorder_traversal(root)前序递归：先取根值，再拼接左子树结果和右子树结果，顺序就是“根→左→右”。
  3. inorder_traversal(root)中序递归：把根值放在左右两段结果中间，实现“左→根→右”。
  4. levelorder_traversal(root)层序 BFS：用 deque 当队列，弹一个节点就把它的两个孩子排到队尾。
  5. morris_inorder(root)Morris 中序：pred 指针负责找左子树最右节点，临时挂线索再回来清除，全程无栈。
  6. build_tree(preorder, inorder)重建二叉树：取前序首元素为根，在中序里定位并用切片切分左右子树，递归构造。
  7. if __name__ == "__main__":程序入口，构造样例树并打印各遍历结果，方便直接运行验证。

常见误区

误区我觉得只要前序序列相同，这两棵二叉树就是同一棵。毕竟列表开头都是同一个根，后面几层看数字顺序也差不多，应该能对得上吧？

正解前序（或后序）单独出现时无法唯一确定树形。比如根为 1、左孩子是 2 的树，前序是 [1,2]；根为 1、右孩子是 2 的树，前序也是 [1,2]。两个序列完全相同，树却长得完全不同。只有“前序 + 中序”或“后序 + 中序”（节点值互异时）才能唯一重建。就像两份族谱名单里，只有一份“按辈分排序”的中序名单配合一份“先长后幼”的前序名单，才能把每个位置对上。

为何常见：人脑天然觉得“序列 = 结构”，忽略了一个序列缺少了“左右子树的边界信息”；只有把两种不同维度的顺序交叉对照，边界才会显形。

误区Morris 遍历要临时修改节点的 right 指针，把树改得乱七八糟，用完之后树不就废了吗？这种算法只能存在于理论题里吧。

正解Morris 确实会临时把左子树最右节点的空 right 指针指向当前节点，但每次利用完线索后，会立刻把它置回 None——走完全程，所有临时改动都被逐一撤销，树结构完好如初。它只是“借粉笔在门框上画记号、登记完就擦掉”，不是把墙拆了。

为何常见：初学者看到“修改指针”就条件反射地警惕，没注意到算法里存在“建立线索”与“清除线索”两个对称动作，本质上是一次完整的借与还。

误区递归版遍历的代码里没写 `stack`、`queue`，只用了函数参数和返回值，所以空间开销应该是 O(1) 吧？

正解递归背后的系统调用栈会为每一层调用保存现场，递归深度等于树高 h，所以空间是 O(h)——最坏情况的斜树会达到 O(n)。这就像你虽然没有随身带登记簿，但每走进一个套间，身后就留了一条“回头路”记录，走廊有多深，记号就有多少。只有 Morris 是真正 O(1) 空间的遍历。

为何常见：人只看见了显式的容器，忘了计算机内部还有隐形的调用栈；面试中“递归是否占空间”是高频陷阱。

误区树的遍历不都应该用递归吗？反正递归能处理所有树的问题，层序我也用它来写。

正解层序是广度优先，天然依赖“先进先出”的次序；递归是深度优先的思考方式，强行用递归模拟层序需要维护额外的高度信息，绕且易错。干净的层序实现就是循环 + 队列：弹一个、登记、把两个孩子入队，没有递归。就像普查按排点名，手里拿的是一张“待访名单”，而不是一头扎进最深的走廊。

为何常见：前中后序都是递归写的，容易让人形成“树 = 递归”的惯性；其实层序的本质是横向推进，和递归的纵向深入是两套心智模型。

误区既然前序+中序能重建，后序+中序也能重建，那前序+后序这种“两个完整序列”总该没问题吧？

正解前序 + 后序通常不能唯一确定二叉树。前序 [1,2]、后序 [2,1] 既可解释为“根 1 带左孩子 2”，也可解释为“根 1 带右孩子 2”，两边信息都分不清左右。只有满二叉树（每个节点度为 0 或 2）时，前序 + 后序才能唯一重建。这好比两份名单都按“先进后出”的同类逻辑记载，缺少了能区分左右维度的第三份参照。

为何常见：直觉认为“序列越多越确定”，没意识到前序和后序描述的是同一种“深度优先”方向，信息冗余却不互补。

面试题

Q1. 二叉树前序遍历的正确访问顺序是？

单选题 · easy

  • A.左 → 根 → 右
  • B.根 → 左 → 右← 正确答案
  • C.左 → 右 → 根
  • D.根 → 右 → 左

答案：B。前序遍历先访问根节点，再递归访问左子树，最后递归访问右子树，口诀“根→左→右”。A 是中序，C 是后序，D 是“反前序”。类比摄影师先拍正堂族长，再进左厢，最后进右厢。

Q2. 对一棵二叉搜索树（BST）进行中序遍历，得到的序列是？

单选题 · easy

  • A.随机乱序
  • B.降序序列
  • C.升序序列← 正确答案
  • D.层序序列

答案：C。BST 左孩子 < 根 < 右孩子，中序按“左→根→右”访问，等价于先输出所有小值再输出根再输出大值，整体必为升序。对应族谱中按辈分从左到右排队，排出来天然有序。

Q3. 对一棵空树（root 为 None）执行任意遍历，返回结果是什么？

单选题 · easy

  • A.抛出异常
  • B.[None]
  • C.[root]
  • D.空列表 []← 正确答案

答案：D。递归遍历的基准条件是“节点为空则返回空列表”，空树没有房间可拜访，名单自然是空的。这也是一般树算法的基础：先判空再递归，保证不越界。

Q4. 已知某二叉树前序序列为 [1, 2, 4, 5, 3, 6, 7]，中序序列为 [4, 2, 5, 1, 6, 3, 7]，该树的根节点是？

单选题 · mid

  • A.4
  • B.1← 正确答案
  • C.7
  • D.无法确定

答案：B。前序序列的第一个元素永远是整棵树的根，所以根为 1。拿到根后再去中序里定位，左边 [4,2,5] 是左子树、右边 [6,3,7] 是右子树。就像前序名单第一个名字必然是正堂族长。

Q5. 已知某二叉树后序序列为 [4, 5, 2, 6, 7, 3, 1]，该树的根节点是？

单选题 · mid

  • A.4
  • B.1← 正确答案
  • C.3
  • D.7

答案：B。后序遍历“左→右→根”，最后一个被访问的才是根节点，所以根为 1。后序像汇总家产：最底层的子孙先登记，族长最后落笔，名单末尾就是全族之主。

Q6. 层序遍历一棵二叉树，最核心的辅助数据结构是？

单选题 · mid

  • A.栈
  • B.队列← 正确答案
  • C.大顶堆
  • D.双向链表

答案：B。层序是广度优先遍历，必须保证“上一层节点先被处理”，这正是队列先进先出（FIFO）的特性。栈只适合深度优先路线，堆和链表不承担这种“按序排队”的组织职责。

Q7. 关于 Morris 遍历，下列说法正确的有？

多选题 · mid

  • A.空间复杂度为 O(1)← 正确答案
  • B.时间复杂度为 O(n)← 正确答案
  • C.必须使用显式栈保存路径
  • D.会临时修改树结构但最终会恢复← 正确答案

答案：ABD。Morris 利用空指针建立临时线索，只用几个指针变量，空间 O(1)，整体时间摊还 O(n)。它不需要显式栈（C 错）；临时线索在使用后会立即清除，树结构恢复原样（D 对）。就像用粉笔在门框画记号、登记完就擦掉。

Q8. 对一棵高度为 h 的完全二叉树执行递归中序遍历，递归调用栈的最大深度约为多少？

单选题 · hard

  • A.O(1)
  • B.O(log n)← 正确答案
  • C.O(n)
  • D.O(n²)

答案：B。递归栈深度等于树的高度。完全二叉树有 n 个节点时高度约为 log₂(n+1)，所以空间是 O(log n)。若是一棵斜树，高度退化为 n，递归栈才会是 O(n)。类比走廊有多深，身后留的回头路记号就有多长。

Q9. 假设每个节点的值互不相同，以下哪些组合能唯一确定一棵二叉树？

多选题 · hard

  • A.前序序列 + 中序序列← 正确答案
  • B.后序序列 + 中序序列← 正确答案
  • C.前序序列 + 后序序列
  • D.仅凭层序序列

答案：AB。中序提供了左右子树的“分界线”，配合前序（或后序）给出的根，即可递归划分并唯一重建。前序+后序缺少左右分界信息，一般无法唯一确定；单独的层序也无法确定树形。只有满二叉树时 C 才可行。

Q10. 对一棵 n 个节点的二叉树执行 Morris 中序遍历，总时间复杂度是？

单选题 · extreme

  • A.O(n log n)
  • B.O(n)← 正确答案
  • C.O(n²)
  • D.O(log n)

答案：B。虽然单次“找左子树最右节点”可能向上爬 O(h)，但每条边在整轮遍历中至多被额外走两趟——设线索一趟、清除线索一趟——所有前驱查找的开销总和仍是 O(n)，摊还后总时间为线性。就像普查员虽然每间房都要画记号，但每扇门最多被画两次粉笔记号，总数与房间数成正比。