Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

4 1 6 3 5 7 2

#include <stdio.h>
#include <stdlib.h>
#define maxn 40 
int n;
int post[maxn],in[maxn];//后序和中序序列
struct node{
  int data;
  struct node *rchild;
  struct node *lchild;
};
struct node *create(int postL,int postR,int inL,int inR){//根据后序和中序创建二叉树
  if(postR<postL)return NULL;//若后序序列 
  struct node *root=(struct node *)malloc(sizeof(struct node));
  root->data=post[postR];//该树根结点为后序序列最后一个数 
  int k;
  for(k=inL;k<=inR;k++)
    if(in[k]==post[postR])break;//在中序序列找到该根节点 
  int ltree=k-inL;//该树左子树结点个数 
  root->lchild=create(postL,postL+ltree-1,inL,k-1);//创建左子树 
  root->rchild=create(postL+ltree,postR-1,k+1,inR);//创建右子树 
  return root;
}
void level(struct node *root){//层次遍历 
  struct node *queue[maxn],*p;
  int front=0,rear=0,i;
  queue[rear++]=root;
  while(rear>front){
     p=queue[front];
     if(p->lchild)queue[rear++]=p->lchild;
     if(p->rchild)queue[rear++]=p->rchild;
     front++;
  }
  for(i=0;i<rear;i++){
    if(i!=0)printf(" ");
    printf("%d",queue[i]->data);
  }   
}
int main(){
  int i;
   scanf("%d",&n);
   for(i=0;i<n;i++)
     scanf("%d",&post[i]);
   for(i=0;i<n;i++)
     scanf("%d",&in[i]);
  struct node *tree=create(0,n-1,0,n-1);
  level(tree);
  return 0;
}