中序+后序还原二叉树：P1030递归分治求先序

1. 题目在说什么两行输入考的是递归分治1.1 来自NOIP 2001的经典小题做题讲究性价比P1030 求先序排列就是一道典型的短小精悍的普及组题。它出自NOIP 2001普及组输入格式极其简单第一行是二叉树的中序遍历字符串第二行是同一棵树的后序遍历字符串要求输出这棵二叉树的先序遍历字符串。树结点用不同的大写字母表示字符串长度不超过8输入数据保证合法。很多初学者看到求先序排列五个字第一反应是先序排列是不是要把中序和后序拿来拼一拼或者是不是要找规律把两个字符串穿插起来如果你也有这个想法那这道题的意义就体现出来了——它真正想让你理解的是二叉树的递归结构而不是字符串的排列组合。我在刷题群里见过不少同学拿到题目先试各种双指针、双循环折腾半小时不如老老实实从后序的最后一个字符就是根这个角度入手。下面我把整道题的推导链路完整拆开。1.2 三种遍历的顺序先捋一遍为了避免后面推导时绕晕先把三种遍历的定义固定下来。假设一棵二叉树有根节点 R、左子树 L、右子树 Rr先序遍历先访问 R再先序遍历 L最后先序遍历 Rr简称根左右。中序遍历先中序遍历 L再访问 R最后中序遍历 Rr简称左根右。后序遍历先后序遍历 L再后序遍历 Rr最后访问 R简称左右根。注意这里的遍历 L不是笼统地访问 L而是再套一遍相同的规则。比如中序遍历的完整定义就是对左子树做中序遍历访问根对右子树做中序遍历。这天然就是递归定义。正因为每一棵子树都遵守同样的顺序规则所以一个遍历序列里其实隐藏着根在哪、左右子树各占多少的信息。中序和后序两条序列放一起恰好把根是谁和左右边界在哪这两条信息都补全了这就是整道题的解题钥匙。2. 核心原理后序最后一个是根中序负责切两半2.1 后序里藏着根的位置后序遍历的最后一个节点一定是整棵树的根。因为后序顺序是左、右、根根压轴出场。同理中序遍历里根一定在序列的某个位置根左边的子串就是左子树的中序遍历根右边的子串就是右子树的中序遍历。只要知道根是谁就能在中序中确定左右子树各自包含哪些节点知道左右子树各有多少个节点就能在后序中精确切出左子树的后序和右子树的后序然后递归处理。这就是整个算法的一行式总结。反过来先序中序也一样先序第一个是根也能分割中序。但先序后序不行这个放到2.3专门说。2.2 用样例完整模拟一遍题目样例给的是中序BADC后序BCDA第一步看后序的最后一个字符A。A 就是整棵树的根。第二步在中序 BADC 里找到 A它在下标1从0开始数。于是左子树的中序BA左边右子树的中序DCA右边左子树有1个节点右子树有2个节点。第三步回到后序 BCDA去掉最后的根 A剩下 BCD。前1个字符是左子树的后序B后面2个字符是右子树的后序CD。此时树结构已经出来了A / \ B D / C第四步递归求左右子树。左子树中序B、后序B唯一确定根B。右子树中序DC、后序CD后序最后一个是D说明D是右子树的根中序DC中D在左边所以C是D的左子树右子树为空。整理一下整棵树先序 A 左子树先序(B) 右子树先序(DC) ABCD对一下样例输出就是 ABCD。这个推导过程很重要别看它简单它已经把递归的两个关键动作都体现出来了一是每次处理后序的最后一个字符作为根二是根据中序里根的位置计算左右子树的节点数量再去切割后序。后面的代码只是把这个过程翻译给计算机。2.3 为什么先序后序不能唯一确定很多同学会问既然中序后序能还原中序先序也能还原那先序后序是不是也可以答案是通常不行。先序序列和后序序列都只告诉我们根在哪一头但当中序缺失时我们无法判断某个内部节点到底只有左孩子还是只有右孩子。比如一棵只有根A和左孩子B的树先序是AB后序是BA一棵只有根A和右孩子B的树先序还是AB后序也还是BA。这两种完全不同的树先序和后序的排列一模一样。所以先序后序无法唯一还原二叉树除非额外约定没有左子树之类的规则。这个知识点前半部分主要是为了让你深刻理解中序的作用就是区分左右这一本质。明白了这一点即使题目变成中序先序求后序你也能快速迁移。3. 递归设计区间参数才是真正的分水岭3.1 先会写子串版本再理解区间版本最朴素的实现是每次递归都传入新的字符串子串。用C的话大概是这样void solve(string in, string post) { if (in.empty()) return; char root post.back(); int pos in.find(root); cout root; solve(in.substr(0, pos), post.substr(0, pos)); solve(in.substr(pos 1), post.substr(pos, in.size() - pos - 1)); }这个写法逻辑和手工推导完全一致但有两个工程上的问题一是字符串拷贝频繁长度小时无所谓长度大了就是O(n^2)以上的额外开销二是substr的参数容易写混特别是右子树的后序子串。所以更推荐用区间下标来做这也是下面要详细讲的。3.2 四个参数把两个序列切成四段递归函数设计成 dfs(l1, r1, l2, r2)含义是当前考虑的中序区间是 in[l1..r1]后序区间是 post[l2..r2]。整个算法每次做三件事取 post[r2] 作为当前子树的根 root在中序区间 [l1..r1] 中找到 root 的位置 pos于是左子树的中序区间为 [l1, pos - 1]长度为 leftLen pos - l1右子树的中序区间为 [pos 1, r1]根据长度切割后序区间左子树的后序区间是 [l2, l2 leftLen - 1]右子树的后序区间是 [l2 leftLen, r2 - 1]。为什么左子树的后序区间起点还是 l2因为后序区间里除了最后一个root前半段长度就是左子树的节点数后半段长度就是右子树的节点数。左右子树的节点总数等于后序区间长度减一这是由后序定义保证的。递归出口是 l1 r1 或 l2 r2也就是区间为空。需要注意左右两个条件通常同时成立但判断任何一个都足够两个都写上更安全。3.3 输出顺序决定先序先序是根左右所以函数体内先输出 root再递归左子树再递归右子树。如果你想返回一个字符串而不是直接打印就把这三部分拼起来root dfs(...) dfs(...)。这个拼接顺序千万别写成左右根那是后序也别写成左根右那是中序。我在批改学生作业时经常看到递归逻辑完全正确最后输出顺序写反非常可惜。另外一个小细节求先序时根信息在递归入口就能输出所以递归函数甚至不需要返回值。这种边递归边输出的写法比赛里最省事。4. 完整可跑的代码C和Python两版4.1 C区间递归版本#include bits/stdc.h using namespace std; string in, post; void dfs(int l1, int r1, int l2, int r2) { if (l1 r1 || l2 r2) return; char root post[r2]; cout root; int pos in.find(root, l1); int leftLen pos - l1; dfs(l1, pos - 1, l2, l2 leftLen - 1); dfs(pos 1, r1, l2 leftLen, r2 - 1); } int main() { cin in post; int n (int)in.size(); dfs(0, n - 1, 0, n - 1); return 0; }逐行解释几个关键点in.find(root, l1)从下标 l1 开始查找 root返回值是 root 在当前中序中的下标。由于数据保证合法不会返回string::npos。leftLen pos - l1左子树节点数也是切分后序的关键。第一个递归左子树的中序是 [l1, pos - 1]后序是 [l2, l2 leftLen - 1]。第二个递归右子树的中序是 [pos 1, r1]后序是 [l2 leftLen, r2 - 1]。4.2 更保险的做法用数组记录中序位置很多选手不习惯 find更愿意在建树前先预处理一个映射数组。因为题目字符串由大写字母构成可以直接开一个大小为128的 int 数组int posInIn[128]; for (int i 0; i n; i) { posInIn[(int)in[i]] i; }递归里就直接int rootPos posInIn[(int)root];然后拿 rootPos 去判断是否在区间内。这样复杂度更干净。同理Python 可以用字典pos_map {ch: i for i, ch in enumerate(inorder)}这个预处理的好处是把查询根在中序里的位置从 O(n) 变成 O(1)递归总复杂度从 O(n^2) 降到 O(n)。对于长度不超过8的数据find 版完全够用但如果题目把数据范围加大到 10^5 级别预处理映射就变成了必选项。这个优化思路值得记下来很多树相关的题都会用到。4.3 Python简洁版如果你用 Python 做这道题字符串切片版反而可读性更高def get_preorder(inorder, postorder): if not inorder: return root postorder[-1] pos inorder.index(root) left_in inorder[:pos] right_in inorder[pos 1:] left_post postorder[:pos] right_post postorder[pos:-1] return root get_preorder(left_in, left_post) get_preorder(right_in, right_post) if __name__ __main__: inorder input().strip() postorder input().strip() print(get_preorder(inorder, postorder))注意right_post postorder[pos:-1]它去掉最后一个 root 之后取中间一段left_post postorder[:pos]是因为左子树节点数恰好等于 pos这个 pos 是中序里根的下标同时也是左子树节点数。为什么因为中序里根左边的字符数就是左子树节点数后序序列里前 pos 个字符正好就是这些左子树节点构成的子序列。这个对应关系是整道题唯一需要绕一下的点想通了代码就是翻译问题了。Python 版的时间复杂度包含切片和index严格说是 O(n^2)但题目 n ≤ 8比赛环境完全够用。如果追求更规范的写法也可以用区间递归加字典映射逻辑和 C 版一致。5. 新手最容易翻车的三个点与调试技巧5.1 区间端点加减一错位这是最经典的坑。切割左子树后序时很多人会误写成dfs(l1, pos - 1, l2, pos - 1)把中序的端点直接套到后序上。中序和后序区间不共享下标体系必须通过 leftLen 换算。我的体会是把中序切出来的左子树长度先写成一个单独变量 leftLen再用它去算后序的区间端点能避免80%的区间错误。还有右子树后序右端点r2 - 1这是后序中的根被去掉后的结果。有人会写r2把根也包进右子树递归结果是死循环或乱序输出。判断自己有没有错造一条只有左孩子的链测试就知道了。5.2 find返回npos的隐患用in.find(root)时如果 root 不在 in 中会返回string::npos也就是一个极大的无符号数。拿它减 l1leftLen 会变成一个莫名其妙的巨大值然后区间越界。虽说题目保证数据合法不会出现这种情况但你在本地造数据测试时如果输入的中序和后序不是同一棵树立刻就会踩中。建议在 find 之后加一句if (pos string::npos) return;或者用预处理数组写一个循环判断 root 是否在区间内这样代码更健壮。另一个容易忽略的点是in.find(root, l1)的意思是从下标 l1 开始找如果 root 实际出现在 l1 左边它也能正常返回但你要的是 root 必须落在 [l1, r1] 内。如果用了自定义查找务必判断pos l1 pos r1。5.3 用打印法亲眼看到递归过程区间递归最容易出bug又最难定位的就是变量值看起来都对了但输出不对。我的习惯是先在入口打印整行参数cout enter: [ l1 , r1 ] [ l2 , r2 ] root root endl;然后观察每一层的 root 是否和手工推导一致左右区间长度对不对如果发现某个递归区间长度和预期不符基本就是 leftLen 算错了。也可以用极小的数据验证边界n 1中序 A、后序 A输出 A。n 2中序 AB、后序 BA这棵树根是 A右孩子 B输出 AB。n 2中序 BA、后序 AB根是 B左孩子 A输出 BA。这三个用例都能过基本说明区间切分没问题。这套最小用例测试法比盯着代码空想高效得多。6. 从P1030延伸出去一类还原题的通法6.1 中序先序求后序的对称写法学会了 P1030中序先序求后序完全就是套模板。先序第一个字符是根把它拿到中序里分割左右然后递归处理左右子树但最后才输出根。伪代码dfs(l1, r1, l2, r2): root pre[l2] pos 根在中序中的位置 leftLen pos - l1 dfs(l1, pos - 1, l2 1, l2 leftLen) dfs(pos 1, r1, l2 leftLen 1, r2) print(root)注意这里先序区间的切割方式和后序略有不同右子树先序起点是l2 leftLen 1。USACO 有一道 American Heritage洛谷 P1827就是这个题正好用来巩固。遇到还原类的题抓住一句口诀就行后序倒数找根、先序正数找根、中序定区间。6.2 从知识到能力不建树的递归遍历思维这道题还有一个隐藏考点即使不真正建出二叉树节点仅靠区间递归就能完成遍历输出。这说明二叉树的遍历本质上依赖的是递归结构而不是物理指针。如果你自己实现一个 TreeNode 结构用递归函数把中序后序还原成真正的树再走一遍先序遍历也能 AC但代码会长很多。在理解区间递归之前先把 TreeNode 版写一遍是一个很好的过渡练习能帮你把字符序列和树形结构对应起来。6.3 后续刷题怎么衔接把 P1030 吃透之后建议顺手做同类的 P1305 新二叉树、P1827 American Heritage横向比较几种还原方式。再往后就可以挑战综合性更强的题目了比如 NOIP 2016 提高组的 P2831 愤怒的小鸟——它表面上和二叉树没关系是搜索加状态压缩但题目分析和递归分治的思维是一脉相承的。很多提高组选手回头看都会发现普及组的 P1030 就是最早帮你建立不要被题目表面吓住先找递归出口这种思维的题。说实话这道题我前前后后给不少人讲过。每次有同学说我看懂了代码但自己写就错我都建议他别背代码把 2.2 那一节样例推导自己手推三遍推到中序切长度后序按长度切区间变成肌肉记忆再上机写代码。这道题不是难题但它是一把很好的钥匙——它让你第一次意识到所谓遍历序列并不是一串没有结构的字符而是递归树在某个顺序规则下留下的投影。把这道题彻底弄懂后面学建树、学树的序列化、学表达式树都会顺很多。如果你现在正卡在 P1030别急每个人都卡过按这个思路慢慢推很快就能 AC。