PAT L2-006. 树的遍历
原题链接
简单
作者:
青丝蛊
,
2021-04-06 16:06:26
,
所有人可见
,
阅读 225
#include <bits/stdc++.h>
using namespace std;
struct
{
int data, l, r;
} tree[35];
int p[35], in[35];
unordered_map<int, int> mp;
int n;
int q = -1;
int build(int inL, int inR, int pL, int pR)
{
if (inL > inR || pL > pR) return -1;
int x = p[pR];
int index = mp[x];
int cnt = index - inL;
int p = ++q;
tree[p].data = x;
tree[p].l = build(inL, index - 1, pL, pL + cnt - 1);
tree[p].r = build(index + 1, inR, pL + cnt, pR - 1);
return p;
}
void bfs(int x)
{
queue<int> que;
que.push(x);
cout << tree[x].data;
while (que.size())
{
int t = que.front();
que.pop();
if (tree[t].l != -1) que.push(tree[t].l), cout << ' ' << tree[tree[t].l].data;
if (tree[t].r != -1) que.push(tree[t].r), cout << ' ' << tree[tree[t].r].data;
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> p[i];
for (int i = 0; i < n; i++) cin >> in[i], mp[in[i]] = i;
build(0, n - 1, 0, n - 1);
bfs(0);
return 0;
}