(dfs) $O(nlogn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
unordered_map<int, int> m;

const int N = 30;
int f[N];
map<int, vector<int>> ans;

// 不用构造树，用层数存答案
void dfs(int l, int r, int depth)
{
    if(l > r) return ;
    int t = l;
    for(int i = l + 1; i <= r; i ++)
        if(m[f[i]] > m[f[t]]) 
            t = i;
    ans[depth].push_back(f[t]);
    dfs(l, t-1, depth+1);
    dfs(t+1, r, depth+1);
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        m[a] = i;
    }

    for(int i = 0; i < n; i ++)  cin >> f[i];

    dfs(0, n-1, 0);

    for(auto &[x, y] : ans)
        for(auto &t : y)
            cout << t << " ";
    return 0;
}