参考文献
https://www.acwing.com/solution/content/57504/
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n = 0;
int in[N], pre[N];
// int l[N], r[N];
unordered_map<int,int> l,r; //注意本题可没有限制节点值的范围,不能再用数组存储左右孩子了
int post[N];
unordered_map<int,int> mp;
int res = 0;
int build(int il ,int ir, int pl, int pr)
{
if(il > ir) return -1;
int root = pre[pl];
int k = mp[root];
l[root] = build(il, k-1, pl+1, pl+k-il);
r[root] = build(k+1,ir, pl+k-il+1, pr);
if(res == 0)
res = root;
return root;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", &pre[i]);
for(int i = 0; i < n; ++i) scanf("%d", &in[i]), mp[in[i]] = i;
int root = build(0, n-1, 0, n-1);
cout << res << endl;
return 0;
}