思路与算法

先序首字符定根，中序分左右子树，递归后序输出；与库内中序加层序求先序、前后序计方案的协议及目标不同。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

每个节点字母唯一，先序第一个字符为当前根；中序根的左边恰为左子树、右边恰为右子树。两段递归完成以后才输出根，符合后序定义。

复杂度

O(n²)最坏时间（根位置查找），O(n)递归栈与输入输出；n至多26。

易错点

空子树立即返回，不把中序右端位置当作子树元素；源字母是小写字符。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
string pre, in;
void go(int p, int l, int n) {
    if (!n)
        return;
    int z = in.find(pre[p], l);
    go(p + 1, l, z - l);
    go(p + 1 + z - l, z + 1, n - (z - l) - 1);
    cout << pre[p];
}
int main() {
    cin >> pre >> in;
    go(0, 0, pre.size());
    cout << "\n";
}