前序、中序、后序只差访问时机,层序差的是一整条队列

二叉树遍历是从根出发把每个节点恰好访问一次,前序在进入子树前访问根,中序在左右子树之间访问根,后序等两棵子树都处理完才访问根,层序则按深度逐层推进。它重要,是因为搜索、序列化、表达式求值和内存释放都建立在某一种顺序之上。最常见的误区是把递归当成慢、把迭代当成省空间,或者以为中序在任何树上都有序、前序加后序就能唯一还原一棵树。读完你能用同一套“访问时机”的框架写出四种遍历,讲清 O(h) 与 O(w) 的空间从哪来,并在深树、共享树和 Morris 线索化之间做出正确取舍。

是什么

二叉树遍历,是从根出发沿着边把每个节点恰好访问一次,并按“根与两棵子树谁先谁后”确定顺序。前序是根、左、右,中序是左、根、右,后序是左、右、根;层序不在这套递归框架里,它按深度从上到下、从左到右逐层推进。

一句话直觉:前三种像同一条环山公路,差别只在经过观景台时先拍照还是后拍照;层序则像按楼层送快递,送完一层再上一层。

典型场景:二叉搜索树的中序输出天然有序,常用于范围查询与第 k 小;前序适合复制、序列化,因为根先于子树出现,反序列化时能立刻消费根再递归建树;后序适合释放内存、计算表达式树,因为子节点必须先于父节点处理;层序适合按层打印、求树宽、找右视图,以及无权图上的最短步数。

核心原理

三种深度优先遍历的定义本身就是递归:处理根、递归左子树、递归右子树,把“访问根”这一行在三个位置间挪动,就得到三种顺序。

def walk(node, order):
    if node is None:
        return
    if order == "pre":
        yield node.val
    yield from walk(node.left, order)
    if order == "in":
        yield node.val
    yield from walk(node.right, order)
    if order == "post":
        yield node.val

递归能工作,靠的是调用栈替你记住“从根走到当前节点经过了谁”。栈的深度等于树高 h,所以额外空间是 O(h):平衡树是 O(log n),退化成链的树是 O(n)。这也解释了为什么递归在深树上会栈溢出——不是算法写错,而是宿主栈有限。CPython 默认递归上限是 1000 层,可以用 sys.setrecursionlimit 调整,但官方文档明确提醒,调得过高可能直接压垮 C 栈。

把递归改成迭代,本质是把隐式调用栈搬到一个显式数组里,空间并不会自动变成 O(1)。前序最简单:根入栈,弹出即访问,再依次压入右、左,利用后进先出保证左子树先被处理。中序要沿左脊一路压栈,走到空再弹出访问,然后转向右子树;循环的每一轮都在重复“把当前节点到最左端这段路径存起来”。后序有两种常见写法:一种是按“根、右、左”压栈,最后把结果整体反转;另一种是用一个 prev 指针记录上一个访问的节点,判断右子树是否已经处理完。前者好写,后者省一次反转。

层序换的是容器而不是顺序:用队列先进先出,弹出节点时把左右孩子入队。想按层分组,就在每轮循环开始时记下队列长度,这个长度就是当前层的节点数;否则不同层会混在一起。层序的空间是 O(w),w 是树的最大宽度,完全二叉树的最后一层接近 n/2,所以“BFS 一定省空间”并不成立。

遍历序列还能反推树形:前序的第一个元素是根,在中序里找到它,左边归左子树、右边归右子树,递归下去就能唯一还原;后序则从最后一个元素取根。这正是面试里“给两种序列重建二叉树”的标准解法,前提是节点值互异且给出的中序本身合法。

还有一条常被忽略的路线是 Morris 遍历:利用叶子节点空着的右指针,指向中序前驱之后的“回到祖先”的位置,从而在 O(1) 额外空间内完成中序。具体做法是,对当前节点找它左子树的最右节点,把该节点的右指针临时指向当前节点;访问完左子树后顺着这条线索回到当前节点,再把指针恢复成空。判断依据很简单:找前驱时如果它的右指针已经指向当前,说明左子树刚走完,这时恢复为空并访问当前节点;否则才建立线索并继续往左走。整棵树每条边最多被走两遍,时间仍是 O(n),代价是遍历期间树的结构被临时改写。后序的 Morris 更绕,通常要挂一个临时根节点,再反转右脊上的节点。

四种遍历的时间都是 O(n),因为每个节点都被常数次访问;真正拉开差距的是辅助空间、是否修改树,以及能不能提前终止。

常见考点与误区

  • “递归慢,改迭代就快”:两者的渐进时间都是 O(n),递归多出的只是函数调用常数;显式栈同样占 O(h) 内存,只有 Morris 才把额外空间降到 O(1)。面试里被追问“迭代版省不省空间”,答“省的是调用栈开销,不是空间复杂度”才准确。
  • “中序遍历就是有序的”:只有二叉搜索树才成立。对任意二叉树,中序只是“左、根、右”的访问顺序,没有任何大小关系保证;把中序结果当排序结果,是典型的概念偷换。
  • “前序加后序能唯一还原一棵树”:不能。必须有一份中序(且节点值互异)才能定位左右子树;前序加后序在节点只有一个孩子时无法判断这个孩子是左还是右。只有当每个节点都有 0 或 2 个孩子时,前序加后序才唯一。
  • “层序用栈也能做”:用栈弹出会优先深入,得到的是深度优先的变体,不是逐层。层序必须用队列;用列表 pop(0) 是 O(n) 的搬移,规模大时要换 deque。
  • “后序迭代就是把前序结果反转”:只有当你先生成“根、右、左”再反转时才成立;若先生成“根、左、右”再反转,得到的是“右、左、根”,不是后序。压栈顺序写反是手写后序最常见的 bug。
  • “Morris 是免费午餐”:它省的是空间,不是时间,常数因子通常更大;遍历中途 break 必须先把线索指针恢复,否则树被永久改坏。多线程共享同一棵树时更不能随手用。

实践建议

  • 按任务反选顺序:BST 范围查询用中序并在越界时剪枝;序列化用前序并写入空标记,反序列化才能递归消费;释放或求值用后序,保证孩子先于父亲;按层统计、右视图、最小深度用层序。先确定“谁必须先于谁”,再选遍历,比背四种模板可靠。
  • 深树默认走迭代:生产代码面对的是外部输入,树高不可控。显式栈版本不会触发语言级递归上限,还能在找到目标时立刻返回;如果坚持递归,至少给深度设上限并监控。Python 里调高 sys.setrecursionlimit 要配合线程栈大小评估,官方文档也提示过高会导致崩溃。
  • Morris 只在“树独占且内存紧”时用:超大索引、只读快照、并发读都不适合;使用时把恢复指针放进 finally,保证异常路径也能还原,并在文档里写清“遍历期间树结构临时改变”。
  • 层序用 deque 加层大小快照:不要在一层里混入下一层;需要记录路径时存父指针或按层复制,别在队列里塞整个路径,否则空间会从 O(w) 涨到 O(n·h)。
  • 测试覆盖五种形状:空树、单节点、全部在左、全部在右、完全二叉树。左斜和右斜最能暴露栈深与压栈顺序问题;再拿递归版和迭代版互相校对输出,比肉眼检查可靠。

一句话总结:四种遍历的差别不在代码行数,而在“何时访问根”,以及“用什么容器记住回去的路”。

相关阅读

← 返回文章志