AcWing 1631. 后序遍历
原题链接
简单
作者:
Once.
,
2025-01-06 22:44:45
,
所有人可见
,
阅读 2
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 50010;
int n;
unordered_map<int, int> l, r, pos;
int pre[N], in[N], post[N], cnt;
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 + 1 + k - 1 - il);
if (ir > k) r[root] = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
return root;
}
void dfs(int root)
{
if (l.count(root)) dfs(l[root]);
if (r.count(root)) dfs(r[root]);
post[cnt++] = 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]);
pos[in[i]] = i;
}
int root = build(0, n - 1, 0, n - 1);
dfs(root);
printf("%d\n", post[0]);
return 0;
}