通过前序后中序恢复后序。
pl, pr, il, ir分别对应前序左端点，右端点，中序左端点，右端点。

前序的pl位置为根节点, 对应中序的k的位置。
那么中序遍历的左树部分：il 到 k - 1;
那么中序遍历的右树部分：k + 1 到 ir;
那么前序遍历的左树部分：pl + 1 到 pl + 1 + k - 1 - il;
那么前序遍历的右树部分：pl + 1 + k - 1 - il + 1 到 pr;

通过哈希表快速查找前序遍历字符对应中序遍历哪个位置。

#include <iostream>
#include <unordered_map>

using namespace std;

string inorder, preorder, posorder;

unordered_map<char, int> pos;

void build(int il, int ir, int pl, int pr)
{
    if (il > ir) return;
    int k = pos[preorder[pl]];
    build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
    posorder += preorder[pl];
}

int main()
{
    cin >> inorder >> preorder;

    int n = inorder.size();
    for (int i = 0; i < n; i ++) pos[inorder[i]] = i;

    build(0, n - 1, 0, n - 1);

    cout << posorder << endl;

    return 0;
}