AcWing 5070. 前序遍历
原题链接
简单
作者:
最后五分钟
,
2024-11-22 00:04:53
,
所有人可见
,
阅读 7
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010;
int a[N];
int b[N];
unordered_map<int,int> mp2;
int ans;
void dfs(int l,int r,int id1,int id2)
{
if(r<l)return;
ans=a[id1];
int ls=id2-l,rs=r-id2;
dfs(l,id2-1,id1-1-rs,mp2[a[id1-1-rs]]);
dfs(id2+1,r,id1-1,mp2[a[id1-1]]);
}
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
mp2[b[i]]=i;
}
dfs(1,n,n,mp2[a[n]]);
cout<<ans<<endl;
return 0;
}