二叉树中序+后续建树,输出层序
//知道前序遍历||后序遍历+中序遍历 --> 完整二叉树
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
const int N=50;
int n;
int inorder[N],postorder[N];
unordered_map<int,int> pos,l,r;
//中序和后序遍历的顺序不同 il ir表示在中序数组中的开始结束位置 pl pr表示在后续数组中开始结束位置
int build(int il,int ir,int pl,int pr)
{
int root = postorder[pr];
int k =pos[root]; // 找根节点在中序中的位置
if(k>il)l[root] = build(il,k-1,pl,k-1-il+pl); //k-1-il = X-pl -->X = k-1-il+pl
if(k<ir)r[root] = build(k+1,ir,k-il+pl,pr-1); //x+1,pr-1
return root;
}
int bfs(int root) //款搜层序输出
{
queue<int> q;
q.push(root);
while(!q.empty())
{
int t = q.front();
q.pop();
cout<<t<<" ";
if(l.count(t))q.push(l[t]);
if(r.count(t))q.push(r[t]);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>postorder[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;
}