题目描述

给出它的后序遍历和中序遍历，请你输出它的层序遍历。

//the level order traversal层序遍历
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>

using namespace std;

const int N = 40;
int n;
int postorder[N],inorder[N];
unordered_map<int,int> l,r,p;
int q[N];

int build(int inl,int inr,int postl,int postr)
{
    int root = postorder[postr];
    int k = p[root];
    if(inl<k) l[root] = build(inl,k-1,postl,postl+(k-1-inl));//左子树
    if(k<inr) r[root] = build(k+1,inr,postl+(k-1-inl)+1,postr-1);//右子树
    return root;
}

void bfs(int root)
{
    // queue<int> q;
    // q.push(root);
    int hh = 0,tt= 0;
    q[0] = root;//插入根节点

    while(hh<=tt)
    {
        // auto t = q.front();
        // q.pop();
        // cout<<t<<' ';
        int t = q[hh++];
        if(l.count(t)) q[++tt] = l[t];//q.push(l[t]);//先插入左子树
        if(r.count(t)) q[++tt] = r[t];//q.push(r[t]);//再插入左子树
    }
    cout<<q[0];
    for(int i = 1; i<n; i++) cout<<' '<<q[i];
    cout<<endl;
}

int main()
{
    cin>>n;
    for(int i = 0; i<n; i++) cin>>postorder[i];
    for(int i = 0; i<n; i++)
    {
        cin>>inorder[i];
        p[inorder[i]] = i;
    }
    int root = build(0,n-1,0,n-1);
    bfs(root);
    return 0;
}