AcWing 1497. 树的遍历
原题链接
简单
作者:
leo123456
,
2020-08-21 16:10:54
,
所有人可见
,
阅读 707
#include<bits/stdc++.h>
using namespace std;
const int N=40;
int n;
int post[N],in[N];
//int l[N],r[N];
unordered_map<int,int> l,r,pos; //这里不确定结点值,可能很大
int build(int il,int ir,int pl,int pr)
{
int root=post[pr];
int k=pos[root];
if(il<k) l[root]=build(il,k-1,pl,pl+(k-1-il)); //存在左子树就递归遍历左子树
if(k<ir) r[root]=build(k+1,ir,pl+(k-1-il)+1,pr-1); //存在右子树,递归遍历右子树
return root; //都不存在,或者已经执行完左右子树的遍历就返回当前的跟结点
}
void bfs(int root)
{
queue<int> q;
q.push(root);
bool flag=true;
while(!q.empty())
{
auto t=q.front();
q.pop();
if(flag)
{
cout<<t;
flag=0;
}
else cout<<' '<<t;
if(l.count(t)) q.push(l[t]);
if(r.count(t)) q.push(r[t]);
//if(l[t]) q.push(l[t]);
//if(r[t]) q.push(r[t]);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>post[i];
for(int i=0;i<n;i++)
{
cin>>in[i];
pos[in[i]]=i;
}
int root=build(0,n-1,0,n-1);
bfs(root);
return 0;
}