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是根。看中序CABA不在最左边也不在最右边它左边是C右边是B。于是左子树中序是C右子树中序是B左右子树各只有一个结点。再看先序序列根A后面是B、C。左子树应该包含k个结点这里左子树只有一个结点所以先序中A后面的第一个结点B应该是左子树先序。但左子树中序是C左子树结点应该是C不是B。集合矛盾先序认为左子树有B中序认为左子树有C。这个候选中序就不可能。这就是“不可能”的本质先序序列规定了一棵树的“入栈顺序”候选中序序列必须能成为某个“出栈顺序”如果某一步把不属于当前子树的结点放到了错误位置递归结构就无法对齐。2.3 中序序列本质上是一个出栈序列理解这一点能让解题速度上一个台阶。二叉树非递归中序遍历过程是这样的从根出发一路把左孩子压入栈中当无路可走时退栈访问栈顶结点然后处理它的右子树。在整个遍历过程中每个结点第一次被遇到的顺序恰好是先序序列。每个结点被退栈访问的顺序恰好是中序序列。所以对同一棵树来说先序序列就是入栈顺序中序序列就是出栈顺序。反过来给定一个先序序列作为入栈顺序一个候选中序序列如果想成为某个二叉树的中序它必须是一个合法的出栈序列。这个结论直接给出一个通用判断算法用一个栈按照先序序列顺序把结点压栈每次压栈后看栈顶是不是等于当前中序序列要访问的结点如果相等就出栈并继续比较最后如果中序序列被完整匹配说明候选合法否则不合法。这也是我推荐考场使用的方法不需要画树不容易出错。3. 三种解法从原理到考场3.1 方法一递归划分递归划分是最接近定义的方法适合刚开始复习时理解原理。手工步骤如下取出先序序列的第一个结点root。在候选中序序列里找到root的位置。root左边的结点集合作为左子树中序右边的作为右子树中序。根据左子树结点个数k把先序序列中root后面第1个到第k个结点划为左子树先序剩下的划为右子树先序。检查左子树的先序集合和左子树的中序集合是否一致右子树同理。不一致直接判断不可能。一致则继续递归检查左右子树。递归全部通过候选合法。这个方法的优点是容易讲清楚原理适合复习初期建立认知。缺点是手算太慢如果题目有四个候选序列每个都要递归好几层草稿纸容易写得乱七八糟。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 GB.A B C D E F GC.D E F G A B CD.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但中序当前位置是AA在栈里但不是栈顶无法弹出。到这里匹配失败。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 后序序列的对称处理如果你遇到“已知后序 候选多个中序”的题记住一句话后序最后一个元素是根其余步骤和中序重建树的过程完全对称。判断过程可以这样拆从后序序列末尾取根。在中序候选序列里找根的位置划分左子树中序和右子树中序。根据结点个数从后序序列开头方向切出左子树后序和右子树后序。检查集合是否一致。递归处理左右子树。因为后序序列的左右子树区间是从前往后排列的切分顺序不像先序那样直观所以更要写清楚每一步。考试时可以在草稿纸上列一个“子树结点数”表避免切分错误。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 从这道题延伸出去的知识点巩固完“判断哪个中序不可能”之后建议顺手复习这些关联内容已知中序 先序重建二叉树。已知中序 后序重建二叉树。二叉搜索树中序遍历的递增性质。非递归中序遍历的栈过程。线索二叉树和中序线索化。二叉树的序列化与反序列化。这几个知识点经常在同一道大题或选择题组里出现。比如中序线索化就依赖对中序遍历过程的深刻理解二叉搜索树的合法性校验本质也是判断“中序是否递增”。把本题的栈模拟思路搞懂后再看这些内容会轻松很多。我个人的复习顺序是先看严蔚敏教材的遍历章节再做王道对应习题然后自己写重建树和判断序列的代码最后回到真题去提速。这样一轮下来“哪个中序不可能”这类题基本不会再丢分。最后留一个建议如果你现在只是刚开始复习不要一上来就追求几十秒解完。先用递归划分把每一步集合匹配写清楚理解透彻后再练栈模拟。真正到考场上你会发现自己已经不需要画完整棵树只要看到根的位置和左右子树集合出现矛盾就能直接锁定答案。这类题最怕的不是不会递归而是在明显不成立的候选序列上反复画树浪费宝贵的考试时间。