AcWing 1631. 后序遍历
原题链接
简单
作者:
RainSure
,
2022-02-26 10:02:47
,
所有人可见
,
阅读 197
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>
using namespace std;
const int maxn = 50010;
unordered_map<int, int> l, r, pos;
int pre[maxn], in[maxn];
int n;
vector<int> res;
int build(int il, int ir, int pl, int pr)
{
int root = pre[pl];
int k = pos[root];
if(il < k) l[root] = build(il, k - 1, pl + 1, pl + (k - 1 - il) + 1);
if(k < ir) r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1 + 1, pr);
return root;
}
void dfs(int root)
{
if(l.count(root)) dfs(l[root]);
if(r.count(root)) dfs(r[root]);
res.push_back(root);
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> pre[i];
for(int i = 0; i < n; i ++){
cin >> in[i];
pos[in[i]] = i;
}
int root = build(0, n - 1, 0, n - 1);
dfs(root);
cout << res[0] << endl;
return 0;
}