2011FDU机试第二题
给定中序和后序遍历序列，输出树的层序遍历序列

输入样例

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例

4 1 6 3 5 7 2

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int idx;
struct node{
    int val;
    node* left;
    node* right;
};
void buildtree(node*& p,vector<int>& mid,vector<int>& post,int l,int r){
    if(l>r)return;
    p=new node;
    p->val=post[idx];
    int tmp=-1;
    for(int i=0;i<(int)mid.size();i++){
        if(mid[i]==post[idx]){
            tmp=i;
            break;
        }
    }
    idx--;
    buildtree(p->right,mid,post,tmp+1,r);
    buildtree(p->left,mid,post,l,tmp-1);
}
int main(){
    int n;
    cin>>n;
    idx=n-1;
    vector<int> mid(n);
    vector<int> post(n);
    for(int i=0;i<n;i++){
        cin>>mid[i];
    }
    for(int i=0;i<n;i++){
        cin>>post[i];
    }
    node* root;
    buildtree(root,mid,post,0,n-1);
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        auto it=q.front();
        q.pop();
        cout<<it->val<<" ";
        if(it->left)q.push(it->left);
        if(it->right)q.push(it->right);
    }
}