P4870 根据先序中序求后序（基础）

解题思路

第一步，弄清三种遍历的顺序。 先序遍历的顺序是"根→左子树→右子树"，中序遍历的顺序是"左子树→根→右子树"，后序遍历的顺序是"左子树→右子树→根"。可以记一句话：名字在前面就先读根，名字在中间就中间读根，名字在后面就最后读根。就像排队发言，谁先说话取决于他站在队伍里的什么位置。

第二步，用先序找到根。 先序遍历的第一个字符一定是整棵树的根。例如先序 ABC，那么根就是 A。

第三步，用中序把树分成两半。 在中序遍历中找到根的位置，根左边的一串字符就是左子树，根右边的一串就是右子树。比如中序 CBA，根 A 在最后一位，那么左子树是 CB，右子树是空的。

第四步，把左右子树当成新问题递归。 在中序里左子树占区间 [l,pos-1]，右子树占 [pos+1,r]。在先序里，根后面紧跟 pos-l 个字符是左子树，剩下的是右子树。不断重复"找根、切两半"，直到区间为空。

第五步，注意输出顺序。 后序要先输出左子树、再输出右子树、最后输出根。所以递归里先处理左边、再处理右边，最后才 cout 根，这样输出的就是后序。

举个例子。 先序 ABC、中序 CBA：根 A 把中序分成左子树 CB，继续处理左子树，根是 B，再把 CB 分成左子树 C，最后按"左右根"输出 C、B、A，得到 CBA，与样例一致。

边界情况。 当区间左端点大于右端点时，说明子树为空，直接返回，不输出任何字符。

参考代码

// 先序+中序求后序：先序首位是根，中序定位根再分左右递归
#include <iostream>
using namespace std;

char pre[30], ino[30];

// 在中序区间[l,r]里找字符ch的位置
int fnd(int l, int r, char ch) {
    for (int i = l; i <= r; i++)
        if (ino[i] == ch) return i;
    return -1;
}

// 递归求后序：先序区间[l1,r1]，中序区间[l2,r2]
void dfs(int l1, int r1, int l2, int r2) {
    if (l1 > r1) return;              // 空子树
    char root = pre[l1];              // 先序第一个是根
    int pos = fnd(l2, r2, root);      // 根在中序中的位置
    int cnt = pos - l2;               // 左子树结点个数
    dfs(l1 + 1, l1 + cnt, l2, pos - 1);   // 递归左子树
    dfs(l1 + cnt + 1, r1, pos + 1, r2);   // 递归右子树
    cout << root;                     // 后序：左右根
}

int main() {
    cin >> pre >> ino;
    int n = 0;
    while (pre[n]) n++;               // 求结点个数
    dfs(0, n - 1, 0, n - 1);
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度。 每个结点都会被当作根处理一次。fnd 每次在中序区间里查找根，最坏（比如链状的树）要 O(n) 时间，n 个结点合计最坏 O(n²)。n 最大只有 26，瞬间完成。

空间复杂度。 递归深度最多是树的高度，最坏 O(n)，存储字符串的数组也是 O(n)，总空间复杂度 O(n)。