问题 C: 还原二叉树

时间限制: 1 Sec

内存限制: 128 MB

提交: 322

解决: 153

题目描述

给一棵二叉树的层序遍历序列和中序遍历序列，求这棵二叉树的先序遍历序列和后序遍历序列。

 

输入

每个输入文件中一组数据。

第一行一个正整数N（1<=N<=30），代表二叉树的结点个数（结点编号为1~N）。接下来两行，每行N个正整数，分别代表二叉树的层序遍历序列和中序遍历序列。数据保证序列中1~N的每个数出现且只出现一次。

 

输出

输出两行，每行N个正整数，分别代表二叉树的先序遍历序列和后序遍历序列。每行末尾不输出额外的空格。

 

样例输入

7

3 5 4 2 6 7 1

2 5 3 6 4 7 1

样例输出

3 5 2 4 6 7 1

2 5 6 1 7 4 3

 

解题思想：

习惯通过静态的方式来处理树的问题了。整个过程相当于模拟二叉树的层次遍历将二叉树还原出来，最后对其进行遍历。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define MAXN 100 5 using namespace std; 6 typedef struct Node{ 7     int v,L,R; 8     Node(){v=L=R=-1;} 9 }Node;10 Node node[MAXN];11 int lt[MAXN],it[MAXN],flag[MAXN],a;12 void pro(int x){13     if(a==0){14         printf("%d",node[x].v);15         a=1;16     }else{17         printf(" %d",node[x].v);18     }19     if(node[x].L!=-1){20         pro(node[x].L);21     }22     if(node[x].R!=-1){23         pro(node[x].R);24     }25 }26 void post(int x){27     if(node[x].L!=-1){28         post(node[x].L);29     }30     if(node[x].R!=-1){31         post(node[x].R);32     }33     if(a==0){34         printf("%d",node[x].v);35         a=1;36     }else{37         printf(" %d",node[x].v);38     }39 }40 int main()41 {42     int n;43     scanf("%d",&n);44     for(int i=0;i
         
          0&&flag[c-1]!=1){61             node[index1].L=i;62             node[i].v=lt[i++];63             c=0;64             while(node[index1].v!=it[c])65             c++;66             flag[c]=1;67         }68         if(c