题目描述

一个二叉树，树中每个节点的权值互不相同。

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

输入格式
第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式
输出一行 N 个整数，表示二叉树的层序遍历。

样例

输入

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 <cstring>
#include <algorithm>
#include <unordered_map>
#include<queue>
using namespace std;
struct node{
    node *left,*right;
    int val;
    node(int x){
        val=x;
        left=right=NULL;
    }
};
const int N=40;
int postorder[N],inorder[N];
unordered_map<int,int> pos;
node* build(int il,int ir,int pl,int pr){
    node * root= new node(postorder[pr]);
    int k=pos[root->val];
    if(k>il) root->left=build(il,k-1,pl,pl+k-1-il);
    if(k<ir) root->right=build(k+1,ir,pl+k-1-il+1,pr-1);
    return root;
}
void bfs(node* root){
    queue<node*> q;
    q.push(root);
    while(q.size()){
        auto t=q.front();
        q.pop();
        cout<<t->val<<" ";
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);
    }
}

int main(void){
    int n;
    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;//记录值对应的位置
    }
    node* root=build(0,n-1,0,n-1);
    bfs(root);
    return 0;
}