考 408 的同学大概率都有过这种体验一道选择题四个选项看起来都对或者看起来都错最后蒙了一个答案还真的就是那个“看起来最像答案”的。2011 年统考数据结构第 5 题就是这种题。题干很简短——给出二叉树的先序遍历序列要求判断哪个中序遍历序列不可能出现。很多人第一次做这道题时会很困惑先序和中序不是能唯一确定一棵二叉树吗那为什么还会出现“不可能”的选项难道任意给出一个中序序列都能构造出一棵满足先序的树这里先给出一个明确判断这道题的核心不是“背遍历规则”而是“理解遍历序列之间的约束关系”。先序序列确定根中序序列确定左右子树的划分两者放在一起本质上是对一棵二叉树做“双重描述”。如果两个序列互相矛盾就无法还原出任何一棵树。2011 年第 5 题考的就是这个矛盾的检测能力。读完这篇文章你会得到三样东西第一一个 30 秒内手算排除错误选项的三步法第二一份可以直接运行的 C/Python 代码用来判断任意“先序中序”组合是否合法第三在合法前提下重建二叉树、输出后序序列的完整实现。这套能力不仅对这道真题有效对以后遇到“后序中序求先序”“层次中序恢复二叉树”这一类题同样适用。1. 2011年第5题到底在考什么这道题出现在 2011 年 408 统考数据结构部分题目本身并不长但错误率一直不低。原因是很多同学对二叉树遍历的理解停留在“能写出递归代码”这个层面却没有理解一个更根本的问题当两个遍历序列同时给出时它们之间有哪些必须满足的约束先回顾一下三种遍历的定义。先序遍历的顺序是“根、左、右”中序遍历的顺序是“左、根、右”后序遍历的顺序是“左、右、根”。注意这里的“根”指的是当前子树的根不是整棵树的根。对于一棵树中的任意一个子树这三个顺序都成立。遍历方式访问顺序核心作用先序遍历根、左、右第一个元素必为整棵树的根中序遍历左、根、右根的位置把左右子树结点分开后序遍历左、右、根最后一个元素必为整棵树的根层次遍历从上到下、从左到右可配合中序恢复二叉树2011 年第 5 题的考法就是给定先序序列让考生在四个中序序列中找出“不可能”的那个。为什么会有“不可能”因为先序序列限定了根的位置而中序序列限定了左右子树的结点集合两者一旦冲突就没有任何一棵二叉树能同时满足这两个序列。从 408 的命题风格来看这道题真正想考查的是“根据两种遍历序列恢复二叉树”的逆向能力。先序中序可以唯一确定一棵二叉树这是教材结论但这个结论成立的前提是“两个序列来自同一棵树”。题目就是把这个前提拿掉让学生判断“给定的两个序列是否真的来自同一棵树”。换句话说它把正向的“给树求序列”变成了逆向的“给序列验树”。这里要特别强调一个判断刷这道题时如果只记住某个选项是答案那这道题就白刷了。因为 408 对遍历序列的考查方式一直在变化但核心逻辑不变。真正要掌握的是“先序定根、中序分割、递归验证”这套通用方法。掌握了它不管选项怎么变你都能在几十秒内完成判断。2. 核心原理先序中序为什么能唯一确定一棵二叉树要理解“哪个中序不可能”首先要理解“先序中序为什么能确定一棵二叉树”。这两个序列之间的关系可以用三个关键观察来概括。第一个观察先序序列的第一个元素一定是整棵树的根结点。因为先序遍历最先访问的就是根这是定义没有任何例外。第二个观察得到根结点之后去中序序列里找到这个根根左边的所有结点一定属于左子树根右边的所有结点一定属于右子树。中序遍历的顺序是“左、根、右”所以根天然地把结点分成左右两个部分。第三个观察也是最重要的左子树和右子树的结点在先序序列中也必须是连续的两段。先序遍历的顺序是“根、左、右”根访问完之后紧接着访问整棵左子树左子树访问完才访问右子树。因此如果中序序列告诉我们左子树有 L 个结点那么先序序列中紧随根之后的 L 个结点必须全部属于左子树集合再往后的结点必须全部属于右子树集合。这三个观察合在一起就构成了“先序中序唯一确定二叉树”的证明过程同时也是判断“序列是否合法”的判定规则。用一个小例子演示这个过程。假设先序序列是 ABDCE中序序列是 DBAEC。先取先序第一个元素 A 作为根在中序 DBAEC 中找到 A位置在中间偏右。A 左边是 DB说明左子树集合是 {D, B}A 右边是 EC说明右子树集合是 {E, C}。再看先序序列 ABDCE。根 A 之后是 B、D、C、E 这 4 个结点。左子树有 2 个结点所以先序中 A 之后的 2 个结点 B、D 必须属于左子树集合确实 {B, D} {D, B}。剩下 C、E 属于右子树集合确实 {C, E} {E, C}。第一层验证通过。接下来递归验证左子树。左子树的先序片段是 BD中序片段是 DB。根是 B中序中 B 的左边是 D说明左子树的左子树是 {D}右子树为空。再看左子树先序 BD根 B 之后是 D正好属于左子树集合。验证通过。右子树同理先序 CE中序 EC根 C左子树 E验证通过。因此这两个序列确实来自同一棵树。这里的关键在于每一次分割后都要用“左子树结点数”去切割先序序列。左子树有多少个结点根后面的前多少个位置就必须是左子树的先序片段。这就是“约束”二字的真正含义。如果某个中序序列给出的左子树集合和先序序列中紧随根后的结点集合对不上那就说明这个中序序列不可能是该先序序列对应的任何一棵二叉树的中序序列。这就是 2011 年第 5 题所有“不可能”选项的根源。3. 手算解法30秒排除不可能的“三步法”选择题不需要真的把整棵树完整还原。绝大多数选项在第一层验证时就能排除。这里给出一个适合考场上使用的手算三步法。3.1 三步法总览第一步确定根。先序序列的第一个元素就是当前子树的根。第二步在中序序列中找到根的位置。根左边有多少个结点就说明左子树有多少个结点根右边有多少个结点就说明右子树有多少个结点。第三步用左子树结点数去切割先序序列。先序序列中根后面的前 L 个结点必须全部来自中序中根左边的集合后 n-L-1 个结点必须全部来自中序中根右边的集合。如果匹配对左子树和右子树继续递归验证如果不匹配直接判定不可能。这个方法的本质就是把“先序中序唯一确定二叉树”的证明过程反着用。每一层只需要做一件事检查“先序中紧跟根的那一段”和“中序中根左右两段”是否集合一致。3.2 手算实例先序 ABCDEF中序 CABDEF用先序 ABCDEF 和中序 CABDEF 走一遍完整流程。先序第一个元素是 AA 就是整棵树的根。在中序 CABDEF 中找到 A位置在第 2 个下标从 1 开始。A 的左边只有一个结点 C说明左子树集合是 {C}左子树大小为 1。A 的右边是 B、D、E、F说明右子树集合是 {B, D, E, F}。现在用左子树大小 1 去切割先序。先序是 A、B、C、D、E、F根 A 之后应该是 1 个左子树结点也就是 B。可是 B 并不在左子树集合 {C} 中而是属于右子树集合。这就矛盾了如果 B 是 A 的左孩子它应该出现在中序 A 的左边但中序 A 的左边只有 C如果 B 不是左孩子那左子树大小就不是 1而先序中 A 后紧接着就是 B这与“先序先遍历左子树”矛盾。所以 CABDEF 不可能成为先序 ABCDEF 对应二叉树的中序序列。整个过程只需要十几秒不需要画树。3.3 容易忽略的递归验证三步法中第三步看起来只是集合判断但要注意集合判断只是必要条件不是充分条件。第一层通过后左右子树内部仍然可能存在矛盾。举例来说先序 ABCDEF中序 CBADEF。第一层检查根 A中序中 A 左边是 CB左子树集合 {C, B}左子树大小 2先序 A 后是 B、C恰好都属于左子树集合右边 D、E、F 都属于右子树集合。第一层通过。但如果就此判定合法是不够严谨的。还要继续看左子树左子树先序片段是 BC中序片段是 CB。根 B中序中 B 的左边是 C左子树集合 {C}左子树大小 1再看先序 BC根 B 后是 CC 确实在左子树集合中验证通过。右子树先序 DEF中序 DEF根 D右子树 EF同样通过。因此 CBADEF 确实合法。在选择题里出题人经常会把干扰项设计成“第一层看起来没问题但子树内部有问题”的形式。所以手算时至少要做到第二层、第三层的递归验证不能只验证根这一层就下结论。4. 完整示例先序 ABCDEF 的四种中序谁不可能下面用一组典型的选项设计来演示完整判断过程。给定先序序列 ABCDEF有四个中序序列候选A. A B C D E FB. B A C D E FC. C B A D E FD. C A B D E F用三步法逐个验证。先看选项 A中序 ABCDEF。根是 A中序中 A 在最左边说明左子树为空右子树结点集合是 {B, C, D, E, F}。先序中 A 后面的 B C D E F 全部属于右子树集合长度也正确。进一步检查右子树先序 BCDEF中序 BCDEF根 B同样结构。这说明整棵树是一条只向右延伸的链A 的右孩子是 BB 的右孩子是 C以此类推。选项 A 合法。再看选项 B中序 BACDEF。根 A 在中序中位于第 2 位左边只有 B左子树集合 {B}右子树集合 {C, D, E, F}。先序中 A 后第一个是 B确实属于左子树集合且左子树大小为 1剩下的 C D E F 属于右子树集合。验证通过。对应树的结构是A 的左孩子是 BA 的右子树是 C-D-E-F 这条右链。选项 B 合法。接着看选项 C中序 CBADEF。根 A 左边是 CB左子树集合 {C, B}大小为 2右边是 DEF右子树集合 {D, E, F}。先序中 A 后是 B、C这两个正好属于左子树集合长度 2后面的 D、E、F 属于右子树集合。第一层通过。再看左子树先序 BC中序 CB根 B左子树为 C可以匹配。选项 C 合法。最后看选项 D中序 CABDEF。根 A 左边只有一个 C左子树集合是 {C}左子树大小为 1右边是 B、D、E、F。先序中 A 后第一个结点是 B但 B 并不在左子树集合 {C} 中而是属于右子树集合。和 3.2 节的分析一样B 的位置无法安放。因此选项 D 是中序序列不可能出现的情况。这道题选 D。选项 D 是很好的干扰项因为它看起来“很有中序的感觉”A 在中间左右各有一堆结点。但正是这种表面上的“合理”让人忽略了先序和中序之间的连续段约束。再换一个角度理解如果把先序序列看成入栈顺序把中序序列看成出栈顺序那么 CABDEF 这个出栈顺序在栈模拟中会在第二个位置卡住。A 入栈后B 入栈此时 B 压在 A 上面如果第一个出栈的是 C那么必须先把 A、B 都压进去C 出栈后栈顶是 B但中序第二个元素是 A而 A 被 B 压住无法立即出栈。矛盾由此产生。这个栈的视角非常重要后面写代码时最简洁的合法性判断就是基于这个思路实现的。5. 代码实现用栈模拟判断中序序列是否合法选择题用手算三步法已经足够。但如果想彻底检验自己的理解或者为复试机试做准备就应该把判断逻辑写成代码。5.1 算法思路先序是入栈序中序是出栈序非递归中序遍历二叉树时会用到栈。中序遍历的访问顺序正好对应着一种“按先序入栈、按中序出栈”的模拟过程先序序列决定结点什么时候入栈中序序列决定结点什么时候出栈。算法过程如下维护一个栈初始为空。用指针 i 指向先序序列表示下一个待入栈的结点。从左到右扫描中序序列的每个字符 c当栈为空或者栈顶元素不等于 c 时不断从先序序列中取元素入栈直到栈顶元素等于 c或者先序序列已经全部入栈。如果先序序列已经用尽栈顶仍然不等于 c说明这个中序序列不可能出现返回 false。如果栈顶等于 c弹出栈顶继续处理中序下一个字符。如果中序序列扫描完说明所有字符都正确匹配返回 true。每个字符最多入栈一次、出栈一次所以时间复杂度是 O(n)其中 n 是序列长度。5.2 C 语言完整实现#include stdio.h #include string.h #include stdbool.h #define MAXN 100 // 判断中序序列 in 是否可能是先序序列 pre 对应二叉树的中序遍历 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; // pre 序列的指针 for (int j 0; j n; j) { // 栈空或栈顶不等于当前中序字符时继续入栈 while (top -1 || stack[top] ! in[j]) { if (i n) { return false; // 先序元素全部入栈仍无法匹配 } stack[top] pre[i]; } // 匹配成功出栈 top--; } return true; } int main() { char pre[MAXN], in[MAXN]; printf(请输入先序遍历序列: ); scanf(%s, pre); printf(请输入中序遍历序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(两个序列长度不一致输入错误\n); return 0; } if (isValidInorder(pre, in, n)) { printf(该中序序列合法对应二叉树存在\n); } else { printf(该中序序列不可能由该先序序列对应的二叉树产生\n); } return 0; }核心逻辑集中在isValidInorder中。stack[top] pre[i]这一步把先序序列中的元素依次压栈直到栈顶能匹配当前要处理的中序字符。如果先序序列已经全部压入栈中还没有匹配成功说明栈里剩余元素的顺序和中序序列冲突该中序序列不合法。编译和运行命令如下gcc btree_inorder_check.c -o btree_inorder_check ./btree_inorder_check输入一组合法序列例如先序 ABCDEF、中序 CBADEF程序输出请输入先序遍历序列: ABCDEF 请输入中序遍历序列: CBADEF 该中序序列合法对应二叉树存在输入一组非法序列例如先序 ABCDEF、中序 CABDEF程序输出请输入先序遍历序列: ABCDEF 请输入中序遍历序列: CABDEF 该中序序列不可能由该先序序列对应的二叉树产生5.3 Python 精简版如果平时用 Python 刷题可以用下面这个更精简的版本def is_valid_inorder(pre: str, in_order: str) - bool: stack [] i 0 for ch in in_order: while not stack or stack[-1] ! ch: if i len(pre): return False stack.append(pre[i]) i 1 stack.pop() return True if __name__ __main__: pre input(请输入先序遍历序列: ).strip() in_order input(请输入中序遍历序列: ).strip() if len(pre) ! len(in_order): print(两个序列长度不一致) elif is_valid_inorder(pre, in_order): print(该中序序列合法对应二叉树存在) else: print(该中序序列不可能由该先序序列对应的二叉树产生)Python 版本的逻辑和 C 版本完全一致。这里要注意一个容易出错的点while not stack or stack[-1] ! ch这个条件中必须先判断栈是否为空再判断栈顶顺序不能写反否则空栈访问stack[-1]会报 IndexError。机试时这个栈模拟函数可以作为判断“遍历序列是否配对”的通用工具也可以进一步用于重建二叉树。6. 进阶合法时重建二叉树并验证后序判断合法性只是第一步。408 的大题和复试机试里经常要求“给定先序和中序重建二叉树并输出后序”。这个需求可以在合法性的基础上直接扩展。6.1 递归重建的核心逻辑构建过程和前面手算三步法一模一样先序片段的第一个元素是根。在中序片段中找到根的位置 pos。中序片段中pos 左边是左子树中序pos 右边是右子树中序。左子树结点数 leftLen pos - inL用它把先序片段切成三部分根、左子树先序、右子树先序。递归构建左右子树。边界条件很简单当先序片段的左边界大于等于右边界时说明没有结点返回 NULL。6.2 C 语言重建并输出后序完整代码#include stdio.h #include stdlib.h #include string.h #include stdbool.h #define MAXN 100 typedef struct TreeNode { char val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 判断中序序列是否可能 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; for (int j 0; j n; j) { while (top -1 || stack[top] ! in[j]) { if (i n) return false; stack[top] pre[i]; } top--; } return true; } // 根据先序和中序重建二叉树 TreeNode *buildTree(const char *pre, int preL, int preR, const char *in, int inL, int inR) { if (preL preR) { return NULL; } TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-val pre[preL]; // 在中序片段中查找根的位置 int pos inL; while (pos inR in[pos] ! pre[preL]) { pos; } int leftLen pos - inL; // 左子树结点数 // 左子树先序 [preL1, preL1leftLen)中序 [inL, pos) node-left buildTree(pre, preL 1, preL 1 leftLen, in, inL, pos); // 右子树先序 [preL1leftLen, preR)中序 [pos1, inR) node-right buildTree(pre, preL 1 leftLen, preR, in, pos 1, inR); return node; } void postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%c, root-val); } int main() { char pre[MAXN], in[MAXN]; printf(请输入先序遍历序列: ); scanf(%s, pre); printf(请输入中序遍历序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(两个序列长度不一致输入错误\n); return 0; } if (!isValidInorder(pre, in, n)) { printf(该中序序列不可能由该先序序列对应的二叉树产生\n); } else { printf(该中序序列合法\n); TreeNode *root buildTree(pre, 0, n, in, 0, n); printf(重建成功后序遍历序列为: ); postorder(root); printf(\n); } return 0; }这段代码把“判断”和“重建”放在了一起。运行示例请输入先序遍历序列: ABCDEF 请输入中序遍历序列: CBADEF 该中序序列合法 重建成功后序遍历序列为: CBFEDA可以用前面的手算过程验证这个后序结果。先序 ABCDEF、中序 CBADEF 对应这棵树A 是根。左子树先序 BC中序 CB根 B左孩子 C。右子树先序 DEF中序 DEF根 D右孩子 EE 的右孩子 F。后序遍历顺序是“左、右、根”C左子树最左叶子、B左子树根、F右子树最右叶子、E、D、A也就是 CBFEDA。和程序输出一致。如果 n 很大递归中用循环找根的位置是 O(n) 的整体会退化到 O(n^2)。面试或机试中更稳妥的做法是先用哈希表记录中序序列中每个字符的下标把查找根的位置优化到 O(1)。哈希优化版本需要注意一个前提二叉树中所有结点值互不相同。如果存在重复值哈希表会丢失信息这也是 408 题目默认的前提条件。7. 常见错误与排查思路代码和手算都容易踩坑。下面把出现频率较高的几个问题整理出来。问题现象可能原因排查方式解决方案手算认为合法程序判断非法两个序列的参数顺序传反或输入时有空格打印 pre 和 in确认谁是谁统一按“先序在前、中序在后”调用元素集合相同但长度一致仍判断非法序列中存在重复字符逐字符检查重复值会导致栈模拟歧义408 默认结点值互异如果确实重复需要带编号处理递归重建时栈溢出二叉树退化成一条链递归深度等于结点数输出树高或检查输入序列是否来自极端树形机试可改用迭代栈模拟笔试直接说明递归思路只验证根一层就下结论左子树或右子树内部仍然存在矛盾对左右子树递归执行三步法至少递归到第二层必要时画树验证哈希优化后结果错误中序存在重复字符哈希表覆盖了位置信息打印哈希表内容检查有重复值时不能直接用普通哈希表其中最常见的问题是把“集合相等”当作“序列合法”。集合相等只是必要条件递归结构也必须一致。比如先序 ABC、中序 CAB根 A 左边是 C右边是 B左子树集合 {C}但先序中 A 后第一个是 BB 不在左子树集合中所以非法。这里的矛盾发生在第一层很容易看出来。但有些题目会把矛盾藏在子树内部第一层集合完全匹配到第二层才暴露。做题时如果遇到两个选项第一层都通过必须继续往下验证子树这就是递归思想的实际应用。另一个高发问题是递归重建时边界写错。buildTree函数里左子树的先序范围是[preL1, preL1leftLen)右子树的范围是[preL1leftLen, preR)。很多同学会把右子树的起点写成preLleftLen少加一个 1导致跳过根结点。判断边界时可以打印每次递归的参数来核对。这个错误在代码中很难一眼发现但一旦输出后序结果完全错乱基本就是边界问题。8. 408复习建议与扩展考点2011 年第 5 题属于“遍历序列恢复二叉树”这一大考点。这类题目在 408 中反复出现而且换汤不换药。下面把这些考点串起来复习效率会高很多。8.1 不同序列组合能否唯一确定二叉树给定序列能否唯一确定二叉树说明先序 中序能先序定根中序分左右后序 中序能后序定根中序分左右层次 中序能层次序定根顺序中序分左右先序 后序不能单孩子结点的左右方向无法区分先序 空指针标记能空指针标记补全了左右子树信息“先序 后序不能唯一确定”这个结论可以用最简反例说明两个结点的树根 A 的左孩子是 B和根 A 的右孩子是 B这两种树的先序序列都是 AB后序序列都是 BA但中序一个是 BA一个是 AB是两棵不同的二叉树。所以考试中只要出现“先序 后序还原二叉树”的说法可以直接判断为错误或需要额外条件。8.2 与本题相似的考法第一类给后序 中序求先序。做法和先序 中序完全对称只是要把“先序第一个元素是根”换成“后序最后一个元素是根”然后同样用中序切割左右子树。第二类给先序 后序问中序有多少种可能。这种题考查的是对“单孩子结点”的理解。每当一个结点只有一个孩子时这个孩子在先序和后序中的相对位置体现不出左右对应中序就多一种可能。第三类在二叉排序树背景下考查遍历。二叉排序树的中序遍历一定是递增序列所以“二叉排序树先序 中序”的组合里中序其实已经隐含了结点之间的顺序关系这类题通常和查找、插入结合。第四类把遍历和栈结合。中序遍历的非递归实现依赖栈所以“先序为入栈顺序、中序为出栈顺序”这个模型本身就是考点。掌握了栈模拟判断法这类题基本是送分题。8.3 复习建议给四个可落地的建议第一先把三种遍历的手算过关包括递归版本和非递归版本。不要只背代码要能在纸上快速写出任意一棵树的先序、中序、后序。第二做“遍历序列恢复二叉树”的专项练习每天手算三题。题目不用很难重点是训练“先序定根、中序分割、左子树长度切先序”这三个动作直到形成条件反射。第三机试必练三件事栈模拟判断合法性、递归重建二叉树、输出另一种遍历验证结果。这三个能力可以互相验证也是复试机试的高频考点。第四错题本里不要只抄原题答案。把“通用解法”写下来比如 2011 年第 5 题的通用解法就是“三步法 递归验证”下次遇到同类题直接调用这套思路而不是回忆上次选的是 A 还是 D。9. 总结与动手练习这篇文章把 2011 年第 5 题背后的逻辑拆成了三层原理层理解先序 中序为什么能唯一确定一棵二叉树手算层用“三步法”快速判断中序序列是否合法代码层用栈模拟判断合法性用递归重建二叉树并输出后序。其中最关键的一个认知是两个序列来自同一棵树时先序序列中紧随根之后的左子树结点段长度必须等于中序序列中根左边结点的数量且这两个集合必须一致。这个约束条件既是证明“唯一确定”的依据也是判断“不可能”的武器。下面留三道练习题建议先手算再用代码验证最后在评论区交流答案。已知先序序列为 ABCDEF中序序列为 CDBAEF这个中序序列是否合法如果合法后序序列是什么已知后序序列为 DEBFCA中序序列为 DBEAFC求先序序列。为什么“先序 后序”不能唯一确定一棵二叉树请画出一个具体反例。把 2011 年第 5 题吃透之后你会明显感觉到408 数据结构中对二叉树遍历的考查表面上是选择题本质上是让你在脑子里维护一棵树。当你面对任意一组先序和中序序列能在几十秒内判断出“这棵树到底存不存在”时这一类题就已经真正通了。