二叉树四种遍历怎么区分：前中后序与层序各解决什么问题

三种递归遍历：差别只有一行

本站前序、中序、后序三个演示页跑的是同一段骨架，唯一的区别是 访问 node 这一行放在哪：

遍历	访问 node 的位置	序列上的特征
前序	两次递归调用之前	第一个元素一定是根
中序	两次递归调用之间	根把序列分成左子树、右子树两段
后序	两次递归调用之后	最后一个元素一定是根

骨架本身只有三行判断：if node 为空: return，然后递归左子树、递归右子树。「访问」插进哪个缝里，就得到哪种遍历。单步演示里你可以盯着高亮行看：前序的高亮总是先落到「访问」再往下钻；后序则要把左右两边都跑完，高亮才回到当前结点。这一步的先后顺序，就是三种遍历的全部区别。

四种遍历各解决什么问题

前序先看见根，适合「照着根往下铺开」的任务：复制一棵树、把树序列化成字符串、打印成层层缩进的目录，都用前序。但只有前序序列无法唯一还原一棵树；前序加中序（且值不重复）才可以。

中序的价值在二叉搜索树上：BST 的中序序列是递增的，所以「跑一遍中序，看结果是否递增」就是检查一棵树是不是 BST 最直接的办法。中序演示页的默认输入就是一棵 BST，你一进去就能看到输出是有序的。

后序是先处理完孩子再回来处理自己，凡是「自底向上」的计算都靠它：释放一棵树的内存、统计每棵子树的大小、算每棵子树的高度，都必须等孩子的结果出来。它的代价是非递归写法最麻烦——需要记住右子树是否已经处理过，否则会重复进入。

层序不是递归，它用一个队列：根入队，每次出队一个结点就访问它，再把它的左右孩子依次入队。层序遍历就是树上的广度优先搜索。想按层分组输出时，在每层开始前记下当时的队列长度即可；反过来，把队列换成栈，访问顺序就变成另一种深度优先，不再按层。

同一棵树上的实测输出

下面这些数字，是在演示台用层序输入写法（8, 3, 10, 1, 6, #, 14, #, #, 4, 7, 13，# 表示空）跑出来的：9 个结点，根是 8，树高 3 层（根在第 0 层，最大深度 3）。四个遍历都按同一份输入测。

遍历	输出序列	演示帧数
前序	8 → 3 → 1 → 6 → 4 → 7 → 10 → 14 → 13	57
中序	1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14	57
后序	1 → 4 → 7 → 6 → 3 → 13 → 14 → 10 → 8	57
层序	8 → 3 → 10 → 1 → 6 → 14 → 4 → 7 → 13	24

对着这张表能核掉三件事：前序首元素是 8、后序末元素是 8，都指向根；中序结果是 1, 3, 4, 6, 7, 8, 10, 13, 14，递增，与「这是棵 BST」一致；层序是 8 | 3, 10 | 1, 6, 14 | 4, 7, 13，一层一层往外铺。

帧数的差别更能说明问题。三种递归遍历都是 57 帧：每个结点要经历「进入 → 访问 → 返回」的完整进出过程，同一批结点被高亮反复经过。层序只有 24 帧，因为每个结点只入队、出队各一次，走完就彻底离开队列，没有回头的动作。你在演示台按前进键时，递归遍历里会看到高亮沿着树「下钻再弹回」，层序里高亮只朝一个方向推进——这就是栈和队列的差别在界面上的样子。

递归栈深度与空间开销

四种遍历的时间复杂度都是 O(n)，因为每个结点恰好被访问一次。差别在空间：

三种递归遍历的额外空间是递归调用栈，深度等于树高 h。平衡树约 log₂n，退化成一条链时是 n。对上面那棵 9 结点、高 3 层的树，栈最深就压 4 层（根到最深叶子这条路径）。

层序的额外空间是队列，宽度等于树最宽一层的结点数 w。上面这棵树第 2 层和第 3 层各有 3 个结点，所以队列里最多同时放 3 个。完全二叉树的最底层约 n/2，这时候 w 是 O(n) 量级——层序在最宽处比递归栈更吃空间，在最深处反而更省。

怎么自己在演示台试

打开前序、中序、后序任意一个演示页，先把默认输入换成 8, 3, 10, 1, 6, #, 14, #, #, 4, 7, 13，单步走到第 3 帧左右，看高亮停在伪代码的哪一行——三个页面在同一个位置会停在不同的行，这就是「访问写在哪」最直观的证据。

再试两次改动：把 6 的两个孩子 4, 7 换成 #，树只剩 7 个结点，重新数一遍帧数，你会看到三种递归遍历的帧数同步变少而层序仍远低于它们；把输入改成一条链（每个结点只留一个左孩子），再看调用栈那一栏的深度，它会一路涨到结点数本身。