已知先序遍历，如何判断哪个中序序列不可能？

考研408真题中有一类题表面在考遍历序列实际在考二叉树的递归定义已知二叉树的先序遍历序列判断哪个中序遍历序列不可能。这类题在2011年统考真题第5题中出现过也是很多辅导书里“看着会做一选就错”的典型。错误往往来自一个直觉先序和中序只要包含相同字符就存在一棵二叉树。这个直觉只对了一半。字符集合相同只是必要条件顺序还必须满足递归约束。因为中序序列一旦确定根的位置就决定了左右子树各有多少个节点先序序列中根之后的节点又必须按“左子树全部节点在前右子树全部节点在后”的顺序出现。这篇文章用一道与2011年第5题同型的模拟题讲透判断方法再给出可直接运行的递归判断代码最后扩展到后序、层序与中序组合的判断思路。学完之后你不只会做这一道题也能理解为什么先序 中序能唯一确定一棵二叉树以及遇到“某个中序序列不可能”时该从哪里检查。1. 从2011年第5题看遍历序列的本质1.1 四种遍历序列分别保留了哪些信息二叉树的递归定义是一棵二叉树要么为空要么由根节点、左子树、右子树三部分组成。四种遍历方式本质上只是选择“根”和“左右子树”的访问顺序遍历方式访问顺序特点先序遍历根、左、右第一个节点一定是整棵树的根中序遍历左、根、右根把左右子树从中间分开后序遍历左、右、根最后一个节点一定是整棵树的根层序遍历按层从左到右第一个节点一定是整棵树的根但层内顺序对子树切分不友好这四种序列中中序序列的作用最特殊它保留了“哪个节点在左子树哪个节点在右子树”的相对位置。先序或后序虽然能确定根的位置但不能单独说明左右子树范围。1.2 中序序列为什么不能独立还原二叉树单独给一个中序遍历序列比如AB能确定唯一二叉树吗不能。AB可以是A 为根B 为右孩子A 为根B 为左孩子B 为根A 为左孩子B 为根A 为右孩子。单看中序你只知道了“左根右”的相对关系但不知道哪个节点是根。只有再给一个先序、后序或层序序列才能把根的位置定下来。反过来单独给一个先序序列也无法确定二叉树。先序AB既可能是 A 的左孩子是 B也可能是 A 的右孩子是 B。和中序配合以后递归结构才能被锁定。1.3 真题通常怎么考查“不可能”2011年第5题这类选择题通常会给出一个确定的先序遍历序列然后给出若干中序序列作为选项问哪个中序序列不可能与这个先序序列来自同一棵二叉树。这种题的难度不在于遍历定义而在于考生是否能从“根 左右子树”的递归角度去验证每个选项。下面用一道同型题作为例子假设一棵二叉树的先序遍历序列为ABDECF下列中序序列中哪个不可能A. DBEAFC B. DEABFC C. ABDECF D. BDAECF E. EABDCF直接肉眼枚举整棵树会非常累。因为先序ABDECF对应的二叉树形态不止一种必须先理解判断规则再处理选项。2. 判断“哪个中序不可能”的核心原理2.1 先序第一个字符是根中序按根切分先序序列的第一个字符一定是整棵树的根。拿到候选的中序序列后第一步就是找到这个根在中序中的位置。例如先序是ABDECF根是A。如果候选中序是DBEAFC那么A在中序的中间位置左边是DBE右边是FC。这意味着左子树的中序序列是DBE右子树的中序序列是FC。如果候选序列里根本找不到A那这个选项直接不可能。2.2 先序剩余序列如何切给左右子树找到根在中序中的位置后可以得到左子树节点数量left_len。接下来关键的一步是先序序列去掉根之后前left_len个节点属于左子树剩余节点属于右子树。为什么可以这样切因为先序遍历的顺序是“根、左、右”。根一旦访问完接下来会完整遍历左子树再完整遍历右子树。所以先序剩余序列中左子树的所有节点必然集中在前面右子树的所有节点必然集中在后面。左子树有多少个节点正好由中序左半部分的长度决定。以前面的数据为例先序: A B D E C F 中序: D B E A F C根A在中序中的位置是下标 3左边长度是 3所以先序去掉 A 后: B D E C F 左子树先序: B D E (前 3 个) 右子树先序: C F (剩余 2 个)这个“用中序左子树长度切先序剩余序列”的规则是整个判断过程的核心。2.3 手工判定流程考场上一旦拿到“已知先序判断某个中序是否可能”的题目可以按下面步骤检查取先序序列第一个字符作为当前子树的根。在候选中序序列中找到这个根的位置。根左边的部分作为左子树中序根右边的部分作为右子树中序。计算左子树中序的长度left_len。在先序序列去掉根之后取前left_len个字符作为左子树先序取剩余部分作为右子树先序。递归对左子树和右子树重复上述过程。如果任意一层出现根在中序中找不到、或者左右子树无法继续满足条件则该中序序列不可能。这个流程既适用于整棵树也适用于每次递归出来的子树。只要所有子树都能成功完成划分该中序序列就与给定先序序列同时存在。2.4 两个典型判定示例先看一个可能的中序序列DBEAFC。先序是ABDECF根是A。在DBEAFC中A的位置是 3左子树中序: D B E 右子树中序: F C 左子树先序: B D E 右子树先序: C F继续看左子树。先序BDE中序DBE根是B。在DBE中B的位置是 1左子树中序: D 右子树中序: E 左子树先序: D 右子树先序: E两个单节点子树都成立。再看右子树。先序CF中序FC根是C在FC中位置是 1左子树中序: F 右子树中序: 空递归成立。因此DBEAFC是可能的。再看一个不可能的中序序列DEABFC。先序根还是A。在DEABFC中A的位置是 2左子树中序: D E 右子树中序: B F C 左子树先序: B D (先序去掉 A 后前 2 个) 右子树先序: E C F问题立刻出现。左子树先序是BD左子树中序是DE。取左子树根B但在中序DE中找不到B。这说明B虽然在中序整体中位于根A的右边可是在先序中它却属于左子树区域。左右子树的节点集合不一致因此DEABFC不可能。3. 写一个递归函数批量判定候选中序3.1 为什么用递归重建而不是肉眼枚举二叉树本身是递归结构判断“一个中序序列是否可能与给定先序共存”的最直接方式就是尝试用这两个序列重建二叉树。如果重建过程中任何一步出现冲突就说明该中序不可能。手工枚举适合少量选项但容易漏掉深层递归冲突。写成递归函数以后无论是考场复盘还是处理更长的序列都可以得到一致结果。3.2 用 Python 实现 can_build下面的can_build函数接收先序序列和中序序列返回布尔值表示这两个序列是否可能来自同一棵二叉树def can_build(preorder: str, inorder: str) - bool: # 两个序列都为空说明子树为空成立 if not preorder and not inorder: return True # 长度不一致直接不可能 if len(preorder) ! len(inorder): return False # 先序第一个字符一定是当前子树的根 root preorder[0] # 在候选中序序列中寻找根的位置 try: idx inorder.index(root) except ValueError: # 中序序列里找不到根不可能 return False # 中序左子树区间 left_in inorder[:idx] # 中序右子树区间 right_in inorder[idx 1:] # 关键用左子树中序的长度去切先序剩余部分 left_len len(left_in) left_pre preorder[1:1 left_len] right_pre preorder[1 left_len:] # 左右子树都必须成立 return can_build(left_pre, left_in) and can_build(right_pre, right_in)这段代码里有几个值得注意的点preorder[0]是当前子树的根不管递归到哪一层都成立。inorder.index(root)用来确定根在中序中的位置。这里要求节点值不重复考研题目默认也是如此。left_len是左子树中序长度也是切割先序剩余序列的唯一依据。递归出口中两个序列都为空才返回True。如果一边为空一边不为空会在长度检查或下一次递归中返回False。3.3 批量判断候选结果把前面的模拟题选项放入脚本preorder ABDECF candidates [ DBEAFC, DEABFC, ABDECF, BDAECF, EABDCF, ] for candidate in candidates: result can_build(preorder, candidate) print(f{candidate}: {possible if result else impossible})运行结果如下DBEAFC: possible DEABFC: impossible ABDECF: possible BDAECF: possible EABDCF: impossible其中ABDECF作为中序序列时对应一棵每个节点都只有右子树的退化二叉树先序和中序恰好相同。这说明先序和中序完全相同也是可能出现的不能因为它“看起来不像”就排除。3.4 进阶用哈希表避免反复查找根上面版本在每次递归中调用index()查找根的位置最坏情况下复杂度是 O(n^2)。对考研题目来说完全够用但如果想写成更通用的工具函数可以先用哈希表记录每个节点在中序中的位置def can_build_fast(preorder: str, inorder: str) - bool: pos {ch: i for i, ch in enumerate(inorder)} def dfs(pre_left: int, pre_right: int, in_left: int, in_right: int) - bool: if pre_left pre_right: return in_left in_right root preorder[pre_left] idx pos.get(root, -1) if idx in_left or idx in_right: return False left_len idx - in_left return ( dfs(pre_left 1, pre_left left_len, in_left, idx - 1) and dfs(pre_left left_len 1, pre_right, idx 1, in_right) ) return dfs(0, len(preorder) - 1, 0, len(inorder) - 1)两个版本判断逻辑一致。索引版减少了字符串切片和查找开销适合在节点数量较多的场景下使用。4. 这类题最容易踩的 4 个坑4.1 用“字符集合相同”代替递归判断最典型的错误是先序和后序包含的字符都一样所以认为中序只要字符一样就可能。为什么错因为字符集合相同只说明树的节点集合一致但中序中每个节点的左右位置还受到递归结构约束。比如先序ABDECF与中序EABDCF字符集合完全相同但中序里根A左边只有一个E先序给左子树分配的前 1 个字符是B两边直接冲突。正确做法是把候选序列放进递归流程里逐步切割而不是比较字符集合。4.2 认为根一定在中序正中间中序顺序是“左、根、右”根看起来应该把中序分成两半。但左右子树完全可能有一边为空。例如先序和中序都是ABDECF时根A在中序的最左边右子树包含全部剩余节点。这种情况下左子树为空根不一定在中间。判断时不要要求根的位置“均匀”或“靠中”只要能找到根并且左右子树都能继续递归即可。4.3 先序剩余序列按肉眼直觉切分拿到先序去掉根后的序列容易凭字符内容去猜“哪个属于左子树哪个属于右子树”。这是不可靠的。切分先序剩余序列的唯一依据是中序左子树的长度。先序中左子树的节点一定整体排在右子树节点前面但每个字符到底属于哪一侧必须通过长度计算不能靠字母顺序或位置猜测。4.4 后序题拿来先序方法硬套如果题目给的是后序序列而不是先序根的位置变成最后一个字符不是第一个字符。后序切割规则是去掉最后一个根后前left_len个字符属于左子树接下来的right_len个字符属于右子树。和先序“根在开头”的处理方向相反。把后序当先序处理是所有遍历组合题里最常见的低级错误。可以整理成一张速查表错误直觉出错原因正确做法字符集合相同就一定能重建忽略递归顺序约束用根在中序中的位置递归切分根一定在中间忘记左右子树可以为空允许根在最左或最右凭直觉划分先序左右子树不知道切分依据按左子树中序长度切分先序后序也取第一个字符当根忘记后序顺序是左右根后序根在最后一个字符5. 推广到后序、层序与中序的组合5.1 后序 中序根在后序末尾后序遍历顺序是“左、右、根”所以后序序列的最后一个字符一定是当前子树的根。判断流程与先序类似只是切割位置不同def can_build_post(postorder: str, inorder: str) - bool: if not postorder and not inorder: return True if len(postorder) ! len(inorder): return False # 后序最后一个字符是根 root postorder[-1] try: idx inorder.index(root) except ValueError: return False left_in inorder[:idx] right_in inorder[idx 1:] left_len len(left_in) # 后序去掉根之后前 left_len 个是左子树剩余是右子树 left_post postorder[:left_len] right_post postorder[left_len:-1] return can_build_post(left_post, left_in) and can_build_post(right_post, right_in)注意right_post使用postorder[left_len:-1]目的就是把最后一个根字符去掉。5.2 层序 中序先过滤左右集合再递归层序遍历的第一个字符是根。找到根以后中序左边和右边分别得到左子树节点集合和右子树节点集合。层序剩余部分中凡是左子树集合里的节点一定属于左子树的层序凡是右子树集合里的节点一定属于右子树的层序。def can_build_level(levelorder: str, inorder: str) - bool: if not levelorder and not inorder: return True if len(levelorder) ! len(inorder): return False root levelorder[0] try: idx inorder.index(root) except ValueError: return False left_in inorder[:idx] right_in inorder[idx 1:] left_set set(left_in) right_set set(right_in) # 从层序剩余部分中过滤出左子树和右子树的层序 left_level [ch for ch in levelorder[1:] if ch in left_set] right_level [ch for ch in levelorder[1:] if ch in right_set] return can_build_level(left_level, left_in) and can_build_level(right_level, right_in)层序与中序组合也能唯一确定二叉树。判断“不可能”的关键同样是递归检查只是不像先序那样可以直接用长度切分层序而是要通过左右子树集合过滤。5.3 不同组合能否唯一确定对比表已知序列能否唯一确定二叉树判断“中序不可能”的主要依据先序 中序能用先序第一个字符当根按中序左子树长度切分先序后序 中序能用后序最后一个字符当根去掉根后按长度切分层序 中序能用层序第一个字符当根按左右集合过滤递归先序 后序一般不能只能确定父子关系左右子树边界不唯一5.4 为什么先序 中序能够唯一确定一棵二叉树每一次递归中先序给出了根中序给出了左右子树的范围。左右子树的范围一旦确定递归规模就确定于是可以在两个序列中继续找下一个子树的根。这个“递归切分”过程可以直接转换成重建代码。工程中常见的表达式树、语法树、序列化二叉树等场景本质上也依赖同样的递归结构。注意这种唯一性成立的前提是二叉树节点值不重复。如果存在重复节点值单独一个字符无法唯一定位根的位置需要额外区分规则。6. 考场做题路径与复习建议6.1 考场 5 步判断法如果考场上遇到“已知先序下列哪个中序不可能”建议按下面路径处理看选项长度排除字符集合与先序不一致的选项。取先序第一个字符作为根在选项的中序里找到根。记录根左侧长度left_len。用left_len切分先序剩余序列得到左右子树先序。检查左右子树先序与左右子树中序是否还能递归匹配。任意一步失败该选项就是“不可能”的候选。如果多个选项看起来都满足不要直接凭整体感觉判断要把递归检查做完。6.2 用代码复盘真题的方法复习时可以把历年真题里的遍历序列选项整理成文本例如每行格式为ABDECF,DBEAFC ABDECF,DEABFC然后用脚本逐行判断import sys for line in sys.stdin: line line.strip() if not line: continue preorder, inorder line.split(,) result can_build(preorder, inorder) print(f{preorder} | {inorder} - {result})这个方法适合在电脑上快速复盘也能让你验证辅导书答案是否可靠。6.3 可复用检查清单做遍历序列组合题之前先对照这份清单[ ] 确认给的是先序、后序还是层序。[ ] 确认根的位置先序取第一个后序取最后一个层序取第一个。[ ] 确认根在中序中是否存在。[ ] 确认左子树中序长度是多少。[ ] 确认另一个序列如何切分左右子树。[ ] 对左右子树递归检查不要只查第一层。[ ] 确认节点值是否唯一不唯一时不能直接用字符定位。[ ] 区分“能唯一确定”和“可能共存”两个概念。6.4 下一步练习方向可以继续做三件事第一把can_build改为返回重建后的树节点而不只是布尔值。输出先序和中序对应的二叉树形态加深对递归切分的理解。第二对同一棵二叉树分别输出先序、中序、后序、层序再写一个“给定两种序列尝试重建二叉树”的小工具用题目数据验证。第三复盘 2010 到 2024 年 408 真题中所有遍历序列选择题。重点不是记住哪道题选哪个选项而是总结“根怎么找、左右子树怎么切、递归到哪里失败”这三件事。二叉树遍历序列问题的核心永远是递归结构。2011年第5题看起来在问“哪个中序不可能”实际是在检验你有没有真正理解根、左子树、右子树三者如何通过序列互相约束。把手工递归流程练熟再把代码跑通这类题后续不会再成为失分点。