由前序/后序+中序求层序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

int n;
const int N = 40;
int postorder[N], inorder[N];
unordered_map<int, int> l, r, pos;

int build(int pl, int pr, int il, int ir)
{
    int root = postorder[pr];
    int k = pos[root];

    if (il < k)
    {
        l[root] = build(pl, pl + k - 1 - il, il, k - 1);
    }
    if (ir > k)
    {
        r[root] = build(pl + k - 1 - il + 1, pr - 1, k + 1, ir);
    }

    return root;
}

void dfs(int root)
{
    queue<int> que;
    que.push(root);
    while (que.size())
    {
        auto t = que.front();
        que.pop();
        cout << t << ' ';
        if (l.count(t))
        {
            que.push(l[t]);
        }
        if (r.count(t)) 
        {
            que.push(r[t]);
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> postorder[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }

    int root = build(0, n - 1, 0, n - 1);
    dfs(root);

    return 0;
}