给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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
代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <stack> using namespace std; const int maxn=50; int mid[maxn],be[maxn]; struct node{ int l,r; }a[maxn]; int rebuild(int la,int ra,int lb,int rb){///a是中序遍历 b是后序遍历 if(ra<la) return 0;///结束条件，很重要。 int rt = be[rb]; int i; ///在中序遍历中找到当前根的位置 for(i = 0;;i++) if(mid[la+i]==rt) break; a[rt].l = rebuild(la,la+i-1,lb,lb+i-1); a[rt].r = rebuild(la+i+1,ra,lb+i,rb-1); return rt;///返回给上一层 } void bfs(int s){ queue<int> q; q.push(s); while(!q.empty()){ int t = q.front(); q.pop(); if(a[t].l!=0) q.push(a[t].l); if(a[t].r!=0) q.push(a[t].r); printf("%d",t); if(!q.empty()) printf(" "); } } int main() { int n; scanf("%d",&n); for(int i = 0; i<n; ++i){ scanf("%d",&be[i]); } for(int i = 0; i<n; ++i){ scanf("%d",&mid[i]); } rebuild(0,n-1,0,n-1); bfs(be[n-1]); return 0; }
