AcWing 1497. 树的遍历
原题链接
简单
作者:
老林的提词器
,
2021-04-11 21:31:03
,
所有人可见
,
阅读 300
#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 40;
int post[N];
int mid[N];
int n;
unordered_map<int,int>pos,r,l;
int q[N];//手动模拟队列
int build(int ml,int mr,int pl,int pr){
int root = post[pr];//根节点为后序遍历最右边的点
int k = pos[root];//根节点在中序遍历中的位置
int len = k - ml;//左子树的长度
if(k>ml) l[root] = build(ml,k-1,pl,pl+len-1);
if(k<mr) r[root] = build(k+1,mr,pl+len,pr-1);
return root;
}
void levelOrder(int root){
int hh=0,tt=0;
q[0] = root;//根节点入队
while(hh<=tt){
int k = q[hh++];//队头元素出队
if(l.count(k)) q[++tt] = l[k];
if(r.count(k)) q[++tt] = r[k];
}
cout<<q[0];
for(int i=1;i<n;i++)
cout<<" "<<q[i];
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>post[i];
for(int i=0;i<n;i++){
cin>>mid[i];
pos[mid[i]] = i;//对中序遍历序列的下标最映射
}
int root = build(0,n-1,0,n-1);
levelOrder(root);
}