二叉树遍历序列判定：先序+后序如何排除不可能的中序？

2011 年 408 统考第 5 题，是数据结构里一道很典型的“遍历序列判断题”。题目给的是二叉树的先序和后序序列，四个选项都是中序序列，让考生选出“不可能”成为该树中序序列的那一个。这类题很多同学拿到手第一反应是“先序和后序不是不能唯一确定二叉树吗”，然后用这个结论去推断，结果发现选项没法排除干净。

这道题其实考查的不是“能不能唯一确定”这种结论，而是你对先序、后序、中序三种遍历过程之间递归约束关系的理解程度。换句话说，它不要求你唯一还原二叉树，只要求你判断某个候选中序是否与给定的先序、后序自洽。今天这篇文章把这类题的通用判定原理讲清楚，再给一套手算流程和一份 Python 判定代码，最后说一说考场上的快速思路和常见误区。无论你是正在备战 408，还是只想把二叉树遍历彻底弄明白，这篇都值得收藏。

1. 这道题到底在考什么

1.1 三种遍历序列各自给出什么信息

二叉树的递归遍历规则本身不复杂：

• 先序遍历：根 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根

很多人只会背这三句话，但到了“给定先序和后序，判断某个中序是否可能”这种题上就不知道怎么用。原因在于没有把遍历序列翻译成“对树结构的约束条件”。

先序遍历序列给的最直接信息是：第一个元素一定是整棵树的根。后序遍历序列给的最直接信息是：最后一个元素一定是整棵树的根。这两个信息叠加，可以立刻锁定根节点。如果题目给的是“先序 + 后序”，那么整棵树的根是唯一的，就是先序第一个元素，也是后序最后一个元素。

中序遍历序列给的信息更关键：根节点把中序序列分成左右两段，左边是左子树的所有节点，右边是右子树的所有节点。正是这个“划分”，让三个序列之间形成了递归验证关系。

1.2 为什么“先序 + 后序”不能唯一确定树

这是不少同学一开始卡住的地方。先序和后序都给出了“根是谁”，但没有给出“哪些节点在左子树、哪些节点在右子树”。例如先序为 A B C，后序为 C B A，根是 A，但 B 和 C 到底在 A 的哪一侧，先序和后序都没有直接说明。

从数学角度看，先序和后续的组合可以对应多棵结构不同的二叉树，它们的先序和后序完全一样。所以“先序 + 后序”不能唯一确定一棵树，这是结论。但第 5 题问的是“哪个中序不可能”，并不是要求你唯一确定树，而是要求你判断候选序列是否与给定的先序、后序同时自洽。结论是：一个中序序列只要能被安排到某棵满足条件的树上，它就是可能的；如果无论怎么安排都矛盾，它就是不可能的。

这不是一个靠“看感觉”能解决的题，它本质是一道递归验证题。

2. 判定“中序不可能”的通用原理

先把判定中序是否可能的原理总结成几条规则。后文的手算流程和代码实现，都是这几条规则的落地。

2.1 根节点必须一致

给定先序序列 pre 和后序序列 post，候选的中序序列 ino 是否能成立，首先要求：

• pre[0] == post[-1]
• 同时 ino 中必须能找到这个根节点

如果某个候选的中序序列里，根节点找不到，直接判定为不可能。这是一条最基础、也最容易被忽略的检查。

2.2 节点集合必须一致

三个序列描述的是同一棵二叉树，所以节点的集合必须完全一致。如果候选的中序序列里出现了一个先序、后序里都不存在的节点，或者少了某个节点，直接排除。

这里有一个隐含细节：序列元素可能重复吗？408 选择题里默认二叉树节点值互不相同，题目如果不特别说明，一般不需要考虑重复值对判定带来的干扰。如果你用代码来做判定，遇到节点值重复的情况，问题会更复杂，需要结合下标、位置信息处理。

2.3 左右子树片段必须连续且对应

中序序列中，根节点把序列分成左子树部分和右子树部分。这两部分的节点集合，必须和先序、后序中切分出来的左右子树片段完全一致。

具体来说：

• 先序序列中，根后面的连续一段属于左子树，再后面连续一段属于右子树
• 后序序列中，开头连续一段属于左子树，再后面连续一段属于右子树，最后才是根

所谓“连续”，是因为遍历过程中一个子树的所有节点是连续输出的，不会出现左子树节点、右子树节点、左子树节点交替出现的情况。这是递归遍历的天然性质。

2.4 空子树对应空片段

这是最容易漏掉的一条判定规则。如果一个节点的中序划分表示它没有左子树，那在对应的先序和后序序列里，左子树的片段也必须为空。绝不能出现“中序里左子树为空，但后序里还有节点堆在根前面”的情况。

上述四条规则，就是这类题完整的判定原理。

3. 手算判定流程

了解了原理之后，下一步是把原理变成可以动手操作的流程。建议考试时按下面的步骤走，速度和准确率都能保证。

3.1 第一步：找根

给定候选中序序列后，先用先序或后序确定整棵树的根。例如先序第一个元素是 A，那么在中序序列中找到 A 的位置。这个位置就是整棵树的左右子树分界线。

3.2 第二步：切分序列

以根在中序中的位置为界，把中序分成左子树序列和右子树序列。同时根据左右子树的节点数量，把先序、后序也切成左右两部分。

注意，切分先序时，先序序列的根后面那一段，要按左子树节点数量来切；切分后序时，也是按左子树节点数量来切。这里的“左子树节点数量”来自中序左半部分的长度。

3.3 第三步：递归验证左右子树

对切分后的左子树和右子树，分别重复第一步到第三步。每次都把“根节点、子树片段、空子树对应”三条规则检查一遍。

如果某一层出现下列任一情况，就可以直接判定“不可能”：

• 先序片段第一个节点和后序片段最后一个节点不一致
• 中序片段中找不到当前子树的根
• 左右子树节点集合与先序、后序对应片段不一致

只有所有子树都通过验证，这个中序序列才是可能的。

3.4 手算时的优先级

考场上时间有限，建议用排除法做题，而不是对每个选项都完整递归到底：

• 先看一眼根在中序中的位置，如果有选项的根位置明显导致左右子树节点数对不上先序、后序片段长度，先排除
• 再检查某个子树片段里，先序或后序的节点集合是否和中序划分一致
• 如果候选选项只剩两个，就用递归判定法仔细验证

下面是这个流程的伪代码：

function is_possible(pre, ino, post): if pre, ino, post 都为空: return True if pre[0] != post[-1]: return False if set(pre) != set(ino) or set(pre) != set(post): return False root = pre[0] idx = ino 中 root 的位置 left_ino = ino[0 : idx] right_ino = ino[idx+1 : ] left_len = length(left_ino) left_pre = pre[1 : 1 + left_len] right_pre = pre[1 + left_len : ] left_post = post[0 : left_len] right_post = post[left_len : len(post)-1] if set(left_pre) != set(left_post) or set(right_pre) != set(right_post): return False return is_possible(left_pre, left_ino, left_post) and is_possible(right_pre, right_ino, right_post)

这个伪代码可以直接翻译成任意一门编程语言。

4. 同型例题手算演示

下面用一道和 2011 年第 5 题同型的例子来演示完整判定过程。例题的节点值均为单个大写字母，且默认互不相同。

已知某二叉树：

• 先序遍历序列：A B D E C
• 后序遍历序列：D E B C A

判断中序序列 D B E A C 是否可能，再判断中序序列 D B E C A 是否可能。

4.1 验证 D B E A C

先序第一个节点是 A，后序最后一个节点也是 A，根确定为 A。在中序 D B E A C 中，A 在第 4 个位置。

于是整棵树的中序划分为：

• 左子树：D B E
• 右子树：C

根据左子树节点数量为 3，切分先序：

• 根：A
• 左子树先序：B D E
• 右子树先序：C

切分后序：

• 左子树后序：D E B
• 右子树后序：C

接下来验证左子树：先序 B D E，后序 D E B，中序 D B E。

此时左子树的根是 B。B 在中序 D B E 中的位置是第 2 个，所以 B 的左子树是 D，右子树是 E。

验证 D：先序 D，后序 D，中序 D，通过。 验证 E：先序 E，后序 E，中序 E，通过。

再验证右子树：先序 C，后序 C，中序 C，通过。

所有子树都通过，所以 D B E A C 是完全合法的中序序列。它对应的二叉树结构如下：

A / \ B C / \ D E

这棵树先序遍历正好是 A B D E C，后序遍历正好是 D E B C A，和中序 D B E A C 完全匹配。

4.2 验证 D B E C A

同样先确定根是 A。中序 D B E C A 中，A 在最后一个位置。于是整棵树的中序划分为：

• 左子树：D B E C
• 右子树：空

先序切分：

• 根：A
• 左子树先序：B D E C
• 右子树先序：空

后序切分：

• 左子树后序：D E B C
• 右子树后序：空

下一步验证左子树：先序 B D E C，后序 D E B C，中序 D B E C。

左子树的根是 B。B 在中序 D B E C 中的位置是第 2 个，所以 B 的左子树是 D，右子树是 E C。

此时问题出现了。B 的右子树中序是 E C，节点集合是 {E, C}。但根据后序 D E B C，B 后面只有一个 C 属于右子树，节点集合是 {C}。两个集合不一致，说明右子树的划分和后序片段对不上。

更直接一点：如果 B 的右子树包含 E 和 C 两个节点，那么这棵子树的后序片段长度应该是 2，但实际能分给右子树的后序片段长度只有 1。这种矛盾说明 D B E C A 不可能成为该二叉树的中序序列。

从这个例子能看出，手算判定时，最关键的一步不是“找根”，而是“切分后比较左右子树的节点集合”。集合一旦对不上，就不要再继续递归了，直接排除。

5. Python 判定函数与测试

如果你不想只靠手算，或者想拿大量题目练习验证，可以写一个递归判定函数。这里给出一份可以直接运行的 Python 实现。

def is_possible(pre: str, ino: str, post: str) -> bool: # 三个序列同时为空时，子树为空，合法 if not pre and not ino and not post: return True if len(pre) != len(ino) or len(pre) != len(post): return False # 根节点必须一致 if pre[0] != post[-1]: return False # 节点集合必须一致 if set(pre) != set(ino) or set(pre) != set(post): return False root = pre[0] idx = ino.find(root) if idx == -1: return False in_left = ino[:idx] in_right = ino[idx + 1:] # 左子树节点数量决定切片位置 left_len = len(in_left) pre_left = pre[1:1 + left_len] pre_right = pre[1 + left_len:] post_left = post[:left_len] post_right = post[left_len:-1] # 左右子树片段节点集合必须一致 if set(pre_left) != set(post_left): return False if set(pre_right) != set(post_right): return False # 递归验证左右子树 return is_possible(pre_left, in_left, post_left) and is_possible(pre_right, in_right, post_right)

使用示例：

pre = "ABDEC" post = "DEBCA" print(is_possible(pre, "DBEAC", post)) # True print(is_possible(pre, "DBECA", post)) # False print(is_possible(pre, "DEBAC", post)) # True print(is_possible(pre, "BEDAC", post)) # True

这段代码的逻辑和手算流程完全一致：找根、切分、验证集合、递归。你可以在本地跑一下，也可以把它改造成批量验证工具，把历年真题的选项一次性判完。需要注意，该实现基于节点值互不相同的假设。如果题目出现重复节点值，需要额外处理重复值时“根”的定位问题。

6. 这类题的考场快速技巧

下面几条是历年考生总结出来的实用技巧，在考场上能明显缩短做题时间。

6.1 先看根位置是否正确

先序第一个节点和后序最后一个节点一定是整棵树的根。把四个选项的中序序列依次看一下，如果某个选项的根位置导致左右子树节点数和先序、后序明显对不上，基本可以直接排除。

例如先序是 A B D E C，后序是 D E B C A，根是 A。如果某个选项把 A 放在最前面，说明整棵树没有左子树，但后序根节点前面还有 4 个节点，这说明这四个节点都必须属于右子树。可先序根节点后面有 B D E C 四个节点，这四个节点如果全部在右子树，和中序“根在最前”是可能匹配的，但后序的顺序也必须能对得上，此时不能只看根位置，还要检查后序整体顺序。

6.2 检查后序片段最后一个节点是否等于当前子树根

递归验证到某一棵子树时，先序片段的第一个节点是当前子树的根，后序片段的最后一个节点也必须是同一个根。如果某一层出现“先序片段第一个节点和后序片段最后一个节点不同”，直接判定不可能。

这一条在手算时特别高效，因为可以在不切分子树的情况下，快速发现矛盾的子树。

6.3 从节点集合不一致入手

当某层中序划分出的左子树节点集合，和先序、后序对应片段集合不一致时，这个选项就不可能。手算时可以优先检查那些“子树节点数比较特殊”的候选。

例如某个子树在中序里只有 1 个节点，但对应的后序片段却有 2 个节点，说明这个候选中序的划分与给定后序冲突，直接排除。

6.4 控制时间，不要每题都递归到底

408 选择题平均每题分配的时间有限。如果遇到判断“哪个中序不可能”的题，先做排除法，通常两轮检查后就能剩下一到两个候选。只有最后剩下的候选才需要完整递归验证。完整递归验证也是在草稿纸上画树结构，不是凭空想象。

7. 常见易混淆点与避坑清单

7.1 “先序 + 中序”和“先序 + 后序”性质不同

这是最大的易混淆点。

• 先序 + 中序：可以唯一确定一棵二叉树
• 后序 + 中序：可以唯一确定一棵二叉树
• 先序 + 后序：不能唯一确定一棵二叉树

很多同学在考场上把“先序 + 后序不能唯一确定树”当成“任何中序都可能”，这是错误理解。不能唯一确定，只代表符合条件的树可能有多棵。但候选中序不一定都能被某棵树满足，有些候选依然与给定的两个序列矛盾。

7.2 不要把“序列合法”和“选项可构造”混为一谈

有些选项看起来顺序怪异，但它可能是合法的。例如某个二叉树只有右子树，中序序列就和先序序列一样。不要因为“中序看着很别扭”就排除掉，一定要按递归验证来判断。

7.3 区分“求后序”和“判断中序不可能”

如果题目是“已知先序和中序，求后序”，那直接递归构建树即可。如果题目是“已知先序和后序，判断中序不可能”，只能用递归验证。两套流程不要混用。

7.4 线索二叉树概念不要混进来

第 5 题考的是遍历序列，不涉及线索二叉树的“前驱”“后继”指针。不要在判定序列时引入线索二叉树的前驱后继关系，那是另一类考点。

8. 备考建议与后续练习方向

这道题属于 408 数据结构里“树与二叉树”板块的经典选择题。备考时建议做三件事。

8.1 刷真题时按题型归类

不只做第 5 题，把所有涉及“遍历序列判断”“由两个序列求第三个序列”的真题放在一起对比。你会发现命题人反复在考同一个底层能力：递归切分左右子树。二叉树遍历的题，本质上是在考递归二段式结构。

8.2 用代码辅助验证

如果你有编程基础，强烈建议把上面这段 Python 判定函数保存下来，再配合往年真题的题目做批量验证。输入题目给的先序、后序，把四个中序选项依次传进去，立刻能知道答案。这个习惯还可以帮你反推题目数据是否可靠，因为有些回忆版真题的序列本身可能不完整。

8.3 练习手画二叉树

考试不能跑代码，手算能力必须过关。建议平时至少手画 20 棵形态不同的二叉树，分别写出先序、中序、后序，再用题目给出的序列互相验证。画多了以后，递归切分的熟练度会明显上升。

9. 总结

2011 年 408 统考第 5 题，考点是二叉树遍历序列的递归约束关系。表面上是“哪个中序不可能”，实际上考查的是你能否通过根节点划分左右子树，并验证先序、后序片段是否自洽。

手算时记住四个要点：根必须一致、节点集合必须一致、子树片段必须连续对应、空子树必须对应空片段。考场上先排除，必要时再递归验证。只要把本文的递归判定流程练熟，这类“判断中序不可能”的选择题不会再成为丢分点。