PAT 1020 Tree Traversal

转自：与后序中序转换为前序的代码相仿（无须构造二叉树再进行广度优先搜索~~），只不过加一个变量index，表示当前的根结点在二叉树中所对应的下标（从0开始），所以进行一次输出先序的递归的时候，就可以把根结点下标所对应的值存储在level数组中（一开始把level都置为-1表示此处没有结点），这样在递归完成后level数组中非-1的数就是按照下标排列的层序遍历的顺序

#include <bits/stdc++.h>
using namespace std;
int level[10000]={
   0};
int post[10000],in[10000],pre[10000];
void build(int begin_in,int begin_post,int begin_pre,int n,int index){if(!n) return;else{int i;int root=post[begin_post+n-1];pre[begin_pre]=root;level[index]=root;for(i=0;i<=n-1;i++){if(root==in[begin_in+i]) break;}int L=i;int R=n-i-1;build(begin_in,begin_post,begin_pre+1,L,index*2);build(begin_in+i+1,begin_post+L,begin_pre+i+1,R,index*2+1);}}
int main(){int t;cin>>t;memset(level,-1,sizeof(level));for(int i=0;i<=t-1;i++){cin>>post[i];}for(int i=0;i<=t-1;i++){cin>>in[i];}build(0,0,0,t,1);int flag=0;for(int i=0;i<10000;i++){if(level[i]!=-1){if(!flag){printf("%d", level[i]); flag=1;} else{printf(" %d",level[i] );}}}return 0;
}