PAT甲级 1020 Tree Traversals 二叉树的中序，后序转层次遍历

思路：

可以先参考：
前序、中序转后序
后序、中序转前序

思路：

后序、中序转层序与后序、中序转前序差不多，主要是我们需要一个index来记录层次遍历中结点的序号。

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int post[35];//后序序列
int in[35];//中序序列
int n;//结点个数
int cnt=0;

struct node{
  int index;
  int key;
}level[35];

bool cmp(node a,node b){
  return a.index<b.index;
}

void level_output(int root,int start,int ends,int index){//层序打印
  if(start>ends){
    return;
  }
  int i=start;
  while(i<ends&&in[i]!=post[root]){//找到中序序列中根结点的位置
    i++;
  }
  level[cnt].key=post[root];
  level[cnt].index=index;
  cnt++;
  level_output(root-(ends-i+1),start,i-1,2*index+1);//遍历左子树
  level_output(root-1,i+1,ends,2*index+2);//遍历右子树
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){//读入后序序列
    cin>>post[i];
  }
  for(int i=0;i<n;i++){
    cin>>in[i];
  }
  level_output(n-1,0,n-1,0);
  sort(level,level+n,cmp);
  for(int i=0;i<n;i++){
    if(i!=n-1){
        cout<<level[i].key<<' ';
    }else{
        cout<<level[i].key;
    }
  }
  return 0;
}