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 空子树对应空片段这是最容易漏掉的一条判定规则。如果一个节点的中序划分表示它没有左子树那在对应的先序和后序序列里左子树的片段也必须为空。绝不能出现“中序里左子树为空但后序里还有节点堆在根前面”的情况。检查项判定条件如果违反根节点pre[0] post[-1]且 ino 中存在该节点不可能节点集合set(pre) set(ino) set(post)不可能子树划分左右子树节点集合与 pre、post 对应片段一致不可能空子树左/右为空时对应片段也必须为空不可能上述四条规则就是这类题完整的判定原理。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[idx1 : ] 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 CB 后面只有一个 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 题考点是二叉树遍历序列的递归约束关系。表面上是“哪个中序不可能”实际上考查的是你能否通过根节点划分左右子树并验证先序、后序片段是否自洽。手算时记住四个要点根必须一致、节点集合必须一致、子树片段必须连续对应、空子树必须对应空片段。考场上先排除必要时再递归验证。只要把本文的递归判定流程练熟这类“判断中序不可能”的选择题不会再成为丢分点。