AcWing 1497. 树的遍历
原题链接
简单
作者:
此间
,
2021-03-24 21:26:06
,
所有人可见
,
阅读 322
#include <bits/stdc++.h>
using namespace std;
const int N=40;
int n;
int posorder[N],inorder[N];//后序遍历,中序遍历
unordered_map<int ,int >l,r,pos;
int build(int il,int ir,int pl,int pr){//中序遍历左端点,中序遍历右端点,后序遍历左端点,后序遍历右端点
int root=posorder[pr];//根节点都必在后续遍历的最后一位
int k=pos[root];//根节点在中序遍历的什么位置
if(il<k)l[root]=build(il,k-1,pl,pl+k-1-il);//在中序遍历和后序遍历中找到左子树所在的位置
if(ir>k)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);//将root值推进队列
while(q.size()){
auto t=q.front();
q.pop();
cout<<t<<" ";
if(l.count(t))q.push(l[t]);//如果t这个值在哈希表里存在,就推入他的子节点
if(r.count(t))q.push(r[t]);
}
}
int main()
{
ios::sync_with_stdio;
cin>>n;
for(int i=0;i<n;i++)cin>>posorder[i];//输入后序遍历
for(int i=0;i<n;i++){
cin>>inorder[i];//输入中序遍历
pos[inorder[i]]=i;//记录中序遍历的位置
}
int root=build(0,n-1,0,n-1);
bfs(root);
return 0;
}