题目大意
给一个二叉树的后序遍历和中序遍历,求层次遍历
建树 dfs
#include<bits/stdc++.h>
using namespace std;
int hou[35],in[35];
struct node
{
int l,r;
}tree[55];
vector<int> ans;
int create(int l1,int r1,int l2,int r2)//1对应后 2对应中
{
if(l2>r2||l1>r1) //递归边界
return 0;
int rt= hou[r1];
int p = l2;
while(in[p]!=hou[r1]) p++;
int cnt = p-l2;
tree[rt].l=create(l1,l1+cnt-1,l2,p-1);
tree[rt].r=create(l1+cnt,r1-1,p+1,r2);
return rt;
}
void dfs(int rt)
{
queue<int> q;
q.push(rt);
ans.push_back(rt);
while(!q.empty())
{
int t=q.front();
q.pop();
if(tree[t].l != 0)
{
q.push(tree[t].l);
ans.push_back(tree[t].l);
}
if(tree[t].r != 0)
{
q.push(tree[t].r);
ans.push_back(tree[t].r);
}
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>hou[i];
}
for(int i =0;i<n;i++)
{
cin>>in[i];
}
create(0,n-1,0,n-1);
dfs(hou[n-1]);
int f = 1;
for(auto it:ans)
{
if(f)
{
f=0;
cout<<it;
}
else
{
cout<<" "<<it;
}
}
cout<<endl;
}