AcWing 1620. Z 字形遍历二叉树
原题链接
简单
作者:
leo123456
,
2020-08-22 20:36:42
,
所有人可见
,
阅读 758
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;
const int N=40;
int n;
int inorder[N],postorder[N];
unordered_map<int,int> pos,l,r;
vector<int> res;
int build(int il,int ir,int pl,int pr)
{
int root=postorder[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 u)
{
queue<int> q;
q.push(u);
bool flag=true;
while(!q.empty())
{
int size=q.size();
for(int i=0;i<size;i++)
{
auto t=q.front();
q.pop();
res.push_back(t);
if(l[t]) q.push(l[t]);
if(r[t]) q.push(r[t]);
}
if(flag)
{
reverse(res.begin()+res.size()-size,res.end());
}
flag=!flag;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>inorder[i];
pos[inorder[i]]=i;
}
for(int i=0;i<n;i++) cin>>postorder[i];
int root=build(0,n-1,0,n-1);
bfs(root);
cout<<res[0];
for(int i=1;i<res.size();i++)
cout<<' '<<res[i];
cout<<endl;
return 0;
}