二叉树遍历序列判断：先序入栈中序出栈，秒解“不可能”中序

2011年408真题第5题，数据结构部分，考了一道很典型的二叉树遍历题：给定先序（或后序）序列后，问哪个中序遍历序列不可能出现。很多考生一看“不可能”三个字就开始画各种二叉树，画出几棵之后发现时间不够，却还是不敢确定答案。实际上，这类题有固定判断思路，不需要把所有候选树都画出来，用“先序序列等同于入栈顺序、中序序列等同于出栈顺序”这个关系，几十秒就能得到确定结果。如果你正在复习408，或者准备期末数据结构，这篇内容值得看完。

我先把结论放在最前面：判断“哪个中序不可能”，最稳的办法不是穷举画树，而是把中序序列当成一个出栈序列来验证。先序序列的第一个元素是根，中序序列中根把结点分成左子树和右子树；一个候选中序序列只要能在“先序入栈、中序出栈”的模拟过程中完整走通，就说明它确实对应某棵二叉树。走不通，就是题目要的不可能序列。

下面按“题目理解、底层原理、解法步骤、完整示例、考场经验、延伸巩固”六个部分拆开讲。

1. 先搞清楚题目在问什么

1.1 三种遍历顺序与“根”的位置

先序遍历的顺序是：根、左子树、右子树。

中序遍历的顺序是：左子树、根、右子树。

后序遍历的顺序是：左子树、右子树、根。

这三句话看起来简单，但做题时很多人用反。关键点只有一个：先序序列的第一个结点是整棵树的根；后序序列的最后一个结点是整棵树的根；中序序列里，根结点把剩下的结点分成两半，左边全是左子树结点，右边全是右子树结点。

举个例子，一棵最简单的二叉树，根是A，左孩子是B，右孩子是C。先序是ABC，中序是BAC，后序是BCA。这里中序的A在中间，B在A左边，C在A右边，这个“左右分割”关系就是解决遍历序列题的核心工具。

1.2 为什么题目偏偏盯上“中序”

选择题里，先序和后序经常一起出现，因为它们一个告诉你根在最前面，一个告诉你根在最后面，定位容易。中序不一样，中序单独看时，你只知道根在某个位置，但不知道根具体是谁；一旦和先序或后序放在一起，中序的定位能力就体现出来了。

更重要的是，先序序列加中序序列可以唯一确定一棵二叉树，后序序列加中序序列也可以唯一确定一棵二叉树。先序加后序却不行，它只能确定根的位置，左右子树边界不清楚。这也是为什么题目很少问“哪个先序不可能”或“哪个后序不可能”，偏偏喜欢问“哪个中序不可能”：中序里的根位置直接决定左右子树划分，只要划分过程出现矛盾，序列就不可能。

1.3 这类题的两种常见问法

第一种问法：给出先序序列，候选多个中序序列，问哪个中序不可能。判断时用先序第一个结点当根，在中序里找根的位置，再检查左右子树集合是否和先序的连续区间一致。

第二种问法：给出后序序列，候选多个中序序列，问哪个中序不可能。判断思路对称，用后序最后一个结点当根，仍然是在中序里找根的位置，再检查左右子树。

无论哪种问法，底层逻辑都是“根定位 + 左右子树集合匹配 + 递归验证”。只要把这个逻辑吃透，题目怎么换都没关系。

2. 判断“不可能”的底层原理

2.1 先序 + 中序为什么能唯一确定一棵二叉树

先序序列的第一个结点是根。拿到根之后，去中序序列里找这个根的位置。根左边的所有结点，一定是左子树的中序序列；根右边的所有结点，一定是右子树的中序序列。

这时再回头数左子树有多少个结点，假设有k个。先序序列中，根后面的前k个结点，就是左子树的先序序列；再往后的所有结点，就是右子树的先序序列。

于是问题被拆成一个更小的子问题：用“左子树的先序 + 左子树的中序”去建左子树；用“右子树的先序 + 右子树的中序”去建右子树。一直递归下去，直到序列为空。这个过程每一步都是确定的，所以先序加中序能唯一确定二叉树。

如果某个候选中序序列不是任何一棵二叉树的中序，那一定是在递归某一步时出现了矛盾。最常见的矛盾是：中序里根左边的结点集合，和先序里对应区间的结点集合对不上。

这里容易有一个误解：觉得只要两边的结点集合一样，就一定合法。其实集合一致只是必要条件，不是充分条件。集合一致后，还要继续递归验证左右子树内部的结构是否也一致。有些序列集合对得上，但递归到深层时依然会卡住。

2.2 不合法序列卡在哪个环节

我用一个简单例子说明。假设先序序列是ABC，某个候选中序序列是CAB。

先序第一个是A，所以A是根。看中序CAB，A不在最左边也不在最右边，它左边是C，右边是B。于是左子树中序是C，右子树中序是B，左右子树各只有一个结点。

再看先序序列，根A后面是B、C。左子树应该包含k个结点，这里左子树只有一个结点，所以先序中A后面的第一个结点B，应该是左子树先序。但左子树中序是C，左子树结点应该是C，不是B。集合矛盾：先序认为左子树有B，中序认为左子树有C。这个候选中序就不可能。

这就是“不可能”的本质：先序序列规定了一棵树的“入栈顺序”，候选中序序列必须能成为某个“出栈顺序”；如果某一步把不属于当前子树的结点放到了错误位置，递归结构就无法对齐。

2.3 中序序列本质上是一个出栈序列

理解这一点，能让解题速度上一个台阶。

二叉树非递归中序遍历过程是这样的：从根出发，一路把左孩子压入栈中；当无路可走时，退栈访问栈顶结点；然后处理它的右子树。

在整个遍历过程中，每个结点第一次被遇到的顺序，恰好是先序序列。每个结点被退栈访问的顺序，恰好是中序序列。所以对同一棵树来说，先序序列就是入栈顺序，中序序列就是出栈顺序。

反过来，给定一个先序序列作为入栈顺序，一个候选中序序列如果想成为某个二叉树的中序，它必须是一个合法的出栈序列。

这个结论直接给出一个通用判断算法：用一个栈，按照先序序列顺序把结点压栈；每次压栈后，看栈顶是不是等于当前中序序列要访问的结点；如果相等，就出栈并继续比较；最后如果中序序列被完整匹配，说明候选合法，否则不合法。

这也是我推荐考场使用的方法，不需要画树，不容易出错。

3. 三种解法，从原理到考场

3.1 方法一：递归划分

递归划分是最接近定义的方法，适合刚开始复习时理解原理。

手工步骤如下：

1. 取出先序序列的第一个结点root。
2. 在候选中序序列里找到root的位置。
3. root左边的结点集合作为左子树中序，右边的作为右子树中序。
4. 根据左子树结点个数k，把先序序列中root后面第1个到第k个结点划为左子树先序，剩下的划为右子树先序。
5. 检查左子树的先序集合和左子树的中序集合是否一致，右子树同理。
6. 不一致，直接判断不可能。
7. 一致，则继续递归检查左右子树。
8. 递归全部通过，候选合法。

这个方法的优点是容易讲清楚原理，适合复习初期建立认知。缺点是手算太慢，如果题目有四个候选序列，每个都要递归好几层，草稿纸容易写得乱七八糟。

3.2 方法二：栈模拟

栈模拟是考场最推荐的方法。

判断规则是这样：把先序序列当作入栈顺序，从头到尾依次把结点压入栈。每压入一个结点，就检查栈顶是不是等于中序序列当前指向的结点。如果相等，就弹出栈顶，中序指针后移，然后继续检查新的栈顶；如果不相等，就继续压入下一个先序结点。

全部先序结点处理完之后，如果中序序列的指针已经走到末尾，说明候选中序是一个合法出栈序列，也就是某棵二叉树的中序；如果中途无法匹配，中序指针没有走完，说明不可能。

我实际做题时的习惯是：不用真正写出完整的栈，只在草稿纸上记录“当前栈顶”和“中序指针位置”，遇到连续出战就写箭头。四个候选序列一轮下来，通常只需要两三分钟。

3.3 方法三：用代码批量验证

如果你在刷题软件或自己电脑上练习，可以写一个判断函数。

def is_possible_inorder(preorder, inorder): stack = [] j = 0 n = len(inorder) for x in preorder: stack.append(x) while stack and stack[-1] == inorder[j]: stack.pop() j += 1 if j >= n: break return j == n

这个函数做的事情就是栈模拟。先序序列中的每个结点依次入栈，栈顶和中序序列当前位置相等就出栈。如果最后中序序列全部匹配，说明候选中序合法。

也可以写递归版判断函数，直接还原“先序 + 中序建树”的过程：

def can_build(preorder, inorder): if not preorder: return True root = preorder[0] if root not in inorder: return False pos = inorder.index(root) left_in = inorder[:pos] right_in = inorder[pos + 1:] left_pre = preorder[1:1 + len(left_in)] right_pre = preorder[1 + len(left_in):] if set(left_pre) != set(left_in): return False if set(right_pre) != set(right_in): return False return can_build(left_pre, left_in) and can_build(right_pre, right_in)

这两个函数可以互相验证。我一般建议：复习时两个都写一遍，理解各自对应的判断逻辑；考场上用栈模拟，因为手算更快。

3.4 三种方法怎么选

递归划分告诉你“为什么”，栈模拟告诉你“怎么做”，代码批量判断告诉你“答案对不对”。三者不冲突，建议按这个顺序掌握。

4. 用一道示例题走完判断流程

4.1 一道示例题

下面用一道同类型示例题走一遍完整流程。候选序列是我为了讲清方法设计的，不是2011年原题选项，但判断思路和真题完全一样。

已知某二叉树先序遍历序列为A B C D E F G，下列哪个中序遍历序列不可能出现？

A.B C A D E F G

B.A B C D E F G

C.D E F G A B C

D.G F E D C B A

四个候选看起来都挺像样。如果靠画树，可能要画出好几棵才放心；用栈模拟，可以直接判断。

4.2 用栈模拟检查四个候选

先定一个判断模板：入栈顺序是A B C D E F G，中序指针指向候选序列第一个元素。

先看第一个候选B C A D E F G。

A入栈，中序第一个元素是B，栈顶是A，不匹配。继续。 B入栈，栈顶是B，等于中序第一个元素B，出栈，中序指针指向C。 C入栈前，栈里只有A，不是C。继续。 C入栈，栈顶是C，等于中序第二个元素C，出栈，中序指针指向A。 此时栈顶是A，等于中序第三个元素A，出栈，中序指针指向D。 D入栈，出栈，中序指针指向E。 E入栈，出栈，中序指针指向F。 F入栈，出栈，中序指针指向G。 G入栈，出栈，中序指针走完。

整个过程没有卡住，所以A是合法中序。它对应一棵左子树稍微偏左、右子树是单链的二叉树。

再看第二个候选A B C D E F G。

A入栈，栈顶A等于中序第一个元素A，出栈。中序指针指向B。 B入栈，出栈。C入栈，出栈。 后面D、E、F、G依次入栈出栈。

完全匹配，所以B合法。这个候选对应的是一棵完全没有右子树的左斜树，或者说每个结点都只有左孩子。

再看第三个候选D E F G A B C。

A入栈，中序第一个元素是D，栈顶A不等于D。 B入栈，栈顶B不等于D。 C入栈，栈顶C不等于D。 D入栈，栈顶D等于中序第一个元素D，出栈。中序指针指向E。 此时栈顶是C，不等于E。 E入栈，栈顶E等于E，出栈。中序指针指向F。 此时栈顶是C，不等于F。 F入栈，栈顶F等于F，出栈。中序指针指向G。 此时栈顶是C，不等于G。 G入栈，栈顶G等于G，出栈。中序指针指向A。 此时栈里从底到顶是A、B、C，栈顶是C，但中序当前位置是A，A在栈里但不是栈顶，无法弹出。

到这里匹配失败。C不是一个合法出栈序列，所以第三个候选不可能。

最后看第四个候选G F E D C B A。

A入栈，中序第一个元素是G，栈顶A不等于G。 B入栈，C入栈，D入栈，E入栈，F入栈，G入栈。 栈顶G等于中序第一个元素G，出栈。中序指针指向F。 栈顶F等于F，出栈。 然后E、D、C、B、A依次出栈。

整个过程非常流畅，最后一个候选合法。它对应一棵只有右子树的右斜树。

4.3 结果整理

四个候选中，只有C在栈模拟过程中卡住，所以“不可能的中序序列”是C。

这个结论用递归划分也能验证：先序第一个是A，候选C中序里A在第四个位置，左子树集合是{D,E,F,G}，右子树集合是{B,C}；但先序序列A后面的前四个结点是B,C,D,E，集合应该是{D,E,F,G}才对，这里出现了B、C混入左子树，集合直接矛盾。不需要继续递归，已经可以判断不可能。

两种方法得到相同结论。考场上先用集合匹配粗筛，再用栈模拟精查，效率最高。

4.4 如果原题给的是后序序列

后序序列的判断思路完全对称。

后序序列的最后一个结点是根，候选序列里根的位置决定左右子树。判断时不再是“后序入栈、中序出栈”的简单栈模拟，但同样可以用递归划分：用后序最后一个结点当根，在中序里找到根，把左右子树分开；再根据左右子树结点个数，从后序序列前面部分切出左右子树的后序区间；逐层检查。

也可以先把后序序列倒过来看，根的位置就变成开头，很多题型可以转化为先序思路。但转化时要注意左右子树的先后顺序会跟着翻转，容易出错。我更建议直接对称递归，而不是强行背一个转化公式。

5. 考场上的时间分配与常见陷阱

5.1 先做根定位和集合匹配

拿到题目后，不要急着对每个候选序列都做完整栈模拟。

第一步，看先序第一个元素，或者后序最后一个元素，确定根是谁。

第二步，对每个候选中序，找到根在哪个位置。如果根左边有m个结点，那么先序序列中根后面的前m个结点，集合必须和这m个结点完全一致。

这一步能快速排除最明显的错误选项。刚才示例里的C，就是被集合匹配直接卡掉。集合匹配能排除的错误，根本不用进栈模拟。

如果集合匹配全部通过，再对剩下的候选做栈模拟。一般408选择题给出的四个候选中，总有一个会在集合层面或递归深层暴露问题。

5.2 不要一上来就画整棵树

很多考生吃亏在画树上。看到先序序列，把根画出来，然后尝试补左右子树；补到一半发现某个候选对不上，但已经浪费了四五分钟。

画树不是不能用，而是要有节制。如果非要画，建议先确定这个候选大概率合法，再画一棵验证结构。对于明显可疑的候选，用栈模拟或集合匹配判断，比画树可靠。

画树还有一个隐患：你对“中序序列”和“树的形状”对应关系不熟时，很容易把左右子树画反。画错之后，后续判断全部失真，越画越慌。

5.3 后序序列的对称处理

如果你遇到“已知后序 + 候选多个中序”的题，记住一句话：后序最后一个元素是根，其余步骤和中序重建树的过程完全对称。

判断过程可以这样拆：

1. 从后序序列末尾取根。
2. 在中序候选序列里找根的位置，划分左子树中序和右子树中序。
3. 根据结点个数，从后序序列开头方向切出左子树后序和右子树后序。
4. 检查集合是否一致。
5. 递归处理左右子树。

因为后序序列的左右子树区间是从前往后排列的，切分顺序不像先序那样直观，所以更要写清楚每一步。考试时可以在草稿纸上列一个“子树结点数”表，避免切分错误。

5.4 常见误区

我总结了几条实际复习中反复出现的错误。

考场时间紧张时，最怕的就是陷入“这个候选好像合法，但我不敢确定”的状态。栈模拟给的是一个机械、明确、可重复的判断标准，比感觉可靠。

6. 结合复习资料怎么巩固和延伸

6.1 王道、严蔚敏教材和王卓课件怎么用

市面上常见的408数据结构资料，对“遍历序列关系”这个考点的覆盖程度不一样。

严蔚敏《数据结构》C语言版，重点看二叉树遍历那几节，尤其是非递归中序遍历和栈的使用。这本书适合建立底层理解，但题目量不大，需要配合习题才够。

王道《数据结构考研复习指导》和天勤的高分笔记，对408出题风格更贴近。它们会把“已知先序中序重建二叉树”“判断遍历序列”这类经典题型整理成专题。做这些专题时，我建议每道题先用递归划分理解，再用栈模拟提速。

王卓老师的PPT课件适合第一轮学习时跟着梳理概念，但不能只看不练。遍历序列关系的知识点，必须通过动手判断才能变成自己的东西，看一百页课件不如亲手推五个候选序列。

6.2 自己出题和验证的小技巧

一个很实用的巩固方法：自己写一个二叉树构建函数，随机生成一棵二叉树，输出它的先序和中序，然后拿这些真实数据当验证集。

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def preorder(root): if not root: return [] return [root.val] + preorder(root.left) + preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right)

生成一批二叉搜索树或普通二叉树后，把先序序列作为输入，把中序序列作为正确答案，再用前面写的is_possible_inorder函数验证。这样既能练习代码能力，又能直观感受“哪些中序序列是合法的”。

我还喜欢做一个小实验：固定先序序列为A B C，把所有可能的中序序列列出来，看看哪些合法、哪些不合法。穷举小规模二叉树后会发现，合法中序序列的个数等于卡特兰数。这个规律可以作为检查答案的依据，而不是计算工具。

6.3 从这道题延伸出去的知识点

巩固完“判断哪个中序不可能”之后，建议顺手复习这些关联内容：

• 已知中序 + 先序，重建二叉树。
• 已知中序 + 后序，重建二叉树。
• 二叉搜索树中序遍历的递增性质。
• 非递归中序遍历的栈过程。
• 线索二叉树和中序线索化。
• 二叉树的序列化与反序列化。

这几个知识点经常在同一道大题或选择题组里出现。比如，中序线索化就依赖对中序遍历过程的深刻理解；二叉搜索树的合法性校验，本质也是判断“中序是否递增”。把本题的栈模拟思路搞懂后，再看这些内容会轻松很多。

我个人的复习顺序是：先看严蔚敏教材的遍历章节，再做王道对应习题，然后自己写重建树和判断序列的代码，最后回到真题去提速。这样一轮下来，“哪个中序不可能”这类题基本不会再丢分。

最后留一个建议：如果你现在只是刚开始复习，不要一上来就追求几十秒解完。先用递归划分把每一步集合匹配写清楚，理解透彻后再练栈模拟。真正到考场上，你会发现自己已经不需要画完整棵树，只要看到根的位置和左右子树集合出现矛盾，就能直接锁定答案。这类题最怕的不是不会递归，而是在明显不成立的候选序列上反复画树，浪费宝贵的考试时间。