PP4869 复原二叉树（基础）

解题思路

第一步，理解题意。 每组数据给两个字符串：一棵二叉树的前序遍历和中序遍历。要用它们还原这棵树，并输出后序遍历。注意输入包含多组数据，直到文件结束，所以要用 while(cin>>pre>>in) 循环来读。

第二步，回忆关键性质。 前序遍历的第一个字符就是根。在中序遍历里找到根，根左边的是左子树的中序，右边的是右子树的中序；再根据左右子树的长度，可以从前序里对应地切出左右子树的前序。

第三步，递归分治。 写函数 post(pl, pr, il, ir) 处理前序区间 [pl,pr] 和中序区间 [il,ir]：取 pre[pl] 为根，在中序里找到根的位置 p，左子树大小 lsz=p-il。左子树是 (pl+1..pl+lsz) 配 (il..p-1)，右子树是 (pl+lsz+1..pr) 配 (p+1..ir)。先递归左、再递归右、最后输出根，正好是后序"左右根"的顺序。

第四步，例子验证。 第一组前序 DBACEGF、中序 ABCDEFG：根是 D，左子树是 BAC、右子树是 EGF，递归下去得到后序 ACBFGED。第二组前序 BCAD、中序 CBAD，得到后序 CDAB，都和样例一致。

第五步，注意细节。 每组字符串长度可能不同，要先求出长度再递归；每个字符串由不重复的大写字母组成，所以最多 26 个结点，递归不会很深，也不用担心数组不够大。

参考代码

// 复原二叉树：多组数据，每组给前序和中序，输出后序
#include <iostream>
using namespace std;

char pre[30], in[30];

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() {
    while (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，速度非常快。