PP4866 已知前中序求后序（基础）

解题思路

第一步，回忆三种遍历。 前序遍历的顺序是"根、左、右"，中序是"左、根、右"，后序是"左、右、根"。现在给了前序和中序，要还原这棵树并输出后序。

第二步，抓住关键：前序第一个就是根。 前序的第一个字母一定是整棵树的根。在中序里找到这个根，根左边的一段就是左子树的中序，右边的一段就是右子树的中序。再根据左右子树的长度，就能从前序里把左右子树的前序也切出来。

第三步，递归解决。 于是问题变成对左、右子树分别做同样的事。写一个函数 post(pl, pr, il, ir) 处理前序区间 [pl,pr] 和中序区间 [il,ir]：取 pre[pl] 为根，在中序里找到它的位置 p，左子树大小 lsz=p-il，然后递归左子树、递归右子树，最后输出根——因为后序是"左右根"，根要放到最后输出。

第四步，例子验证。 前序 ABCDE，中序 BADCE：根是 A，中序里 A 左边是 B，右边是 DC，于是左子树只有 B，右子树由 C、D、E 组成。继续分解：右子树根是 C，左 D 右 E。后序结果：B、D、E、C、A，即 BDECA，与样例一致。

第五步，注意边界。 递归到区间为空时（pl>pr）直接返回，这是递归的终止条件，一定不能漏掉。

参考代码

// 已知前中序求后序：前序第一个是根，在中序里找根分出左右子树
#include <iostream>
using namespace std;

char pre[30], in[30];

// 递归输出前序区间 [pl,pr]、中序区间 [il,ir] 的后序
void post(int pl, int pr, int il, int ir) {
    if (pl > pr) return;
    char root = pre[pl];        // 前序第一个就是根
    int p = il;
    while (in[p] != root) ++p;  // 在中序里找到根的位置
    int lsz = p - il;           // 左子树的大小
    post(pl + 1, pl + lsz, il, p - 1);  // 左子树
    post(pl + lsz + 1, pr, p + 1, ir);  // 右子树
    cout << root;               // 后序顺序：左右根
}

int main() {
    cin >> pre >> in;
    int len = 0;
    while (pre[len]) ++len;
    post(0, len - 1, 0, len - 1);
    cout << endl;
    return 0;
}

复杂度分析

每个结点只被当作根处理一次，递归中输出每个结点一次，所以时间复杂度是 O(n^2)（每次在中序里找根要扫描当前区间），n 是结点个数且最多 26，速度毫无压力。递归栈深度为 O(n)，空间也是 O(n)。