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开始数）。于是：
- 左子树的中序：B（A左边）
- 右子树的中序：DC（A右边）
左子树有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，也就是一个极大的无符号数。拿它减 l1，leftLen 会变成一个莫名其妙的巨大值，然后区间越界。虽说题目保证数据合法，不会出现这种情况，但你在本地造数据测试时，如果输入的中序和后序不是同一棵树，立刻就会踩中。建议在 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。
