L2-006 树的遍历（25 分）
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7输出样例：
4 1 6 3 5 7 2
1 #include<iostream> 2 #include<queue> 3 #include <vector> 4 #include <cstdio> 5 using namespace std; 6 const int N =100; 7 struct Node{ 8 int l,r; 9 }e[N]; 10 int ba[N],mid[N],qi[N],n; 11 //la ra 中序 12 //lb rb 后序 13 /* 14 int build(int la,int ra,int lb,int rb){ 15 if (la>ra) return 0; 16 int rt = ba[rb]; 17 int p1=la,p2; 18 while(mid[p1]!=rt) p1++; 19 p2=p1-la; 20 e[rt].l=build(la,p1-1,lb,lb+p2-1); 21 e[rt].r=build(p1+1,ra,lb+p2,rb-1); 22 return rt; 23 } 24 */ 25 //la ,ra 先序 26 //lb ,rb 中序 27 int build(int la,int ra,int lb,int rb){ 28 if(lb>rb) return 0; 29 int rt = qi[la]; 30 int p1=lb,p2; 31 while(mid[p1]!=rt) p1++; 32 p2=p1-lb; 33 e[rt].l=build(la+1,la+p2,lb,p1-1); 34 e[rt].r=build(la+p2+1,ra,p1+1,rb); 35 return rt; 36 } 37 /* 38 //先序输出 39 void dfs(int rt){ 40 printf("%d ",rt); 41 if(e[rt].l) dfs(e[rt].l); 42 if(e[rt].r) dfs(e[rt].r); 43 } 44 45 46 */ 47 /* 48 //中序输出 49 void dfs(int rt){ 50 if(e[rt].l) dfs(e[rt].l); 51 printf("%d ",rt); 52 if(e[rt].r) dfs(e[rt].r); 53 } 54 */ 55 /* 56 //后序输出 57 void dfs(int rt){ 58 if(e[rt].l) dfs(e[rt].l); 59 if(e[rt].r) dfs(e[rt].r); 60 printf("%d ",rt); 61 } 62 */ 63 /*
//层序输出
64 void dfs(int s){ 65 queue<int>Q ; 66 vector<int>ve; 67 Q.push(s); 68 while(!Q.empty()){ 69 int u=Q.front(); 70 Q.pop(); 71 ve.push_back(u); 72 if(e[u].l) Q.push(e[u].l); 73 if(e[u].r) Q.push(e[u].r); 74 } 75 for(int i=0;i<ve.size();i++){ 76 printf("%d%c",ve[i],i==ve.size()-1?' ':' '); 77 } 78 } 79 */ 80 81 int main() 82 { 83 scanf("%d",&n); 84 for(int i=1;i<=n;i++) { 85 scanf("%d",&qi[i]); 86 } 87 for(int i=1;i<=n;i++){ 88 scanf("%d",&mid[i]); 89 } 90 build(1,n,1,n); 91 int rt=qi[1]; 92 dfs(rt);//根 93 return 0; 94 }