L2-006 树的遍历 （25 分)
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2二叉树：
前(先)序遍历：根左右
中序遍历：左根右
后序遍历：左右根(最后一个为根节点)
层序遍历：BFS从上到下，从左到右
前三个可以通过递归实现，最后一个BFS。
传送门：
代码:
1 //L2-006 树的遍历-二叉树的后序遍历、中序遍历、层序遍历 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=1e5+10; 6 7 struct node{ 8 int l,r; 9 }tree[maxn]; 10 11 int beh[maxn],mid[maxn]; 12 13 int build(int la,int ra,int lb,int rb)//la,ra为中序遍历的, lb,rb为后序遍历的 14 { 15 if(la>ra) return 0; 16 int rt=beh[rb];//根节点为后序遍历的最后一个 17 int p1=la; 18 while(mid[p1]!=rt) p1++;//找到根节点的位置下标 19 int p2=p1-la; 20 tree[rt].l=build(la,p1-1,lb,lb+p2-1);//递归建左子树 21 tree[rt].r=build(p1+1,ra,lb+p2,rb-1);//递归建右子树 22 // cout<<rt<<endl; 23 return rt;//返回值为结束的根节点值 24 } 25 26 void bfs(int x)//bfs求得层序遍历 27 { 28 vector<int> vec; 29 queue<int> que; 30 que.push(x); 31 while(!que.empty()){ 32 int ret=que.front(); 33 que.pop(); 34 if(ret==0) break; 35 vec.push_back(ret); 36 if(tree[ret].l!=0){//左子树不为空 37 que.push(tree[ret].l); 38 } 39 if(tree[ret].r!=0){//右子树不为空 40 que.push(tree[ret].r); 41 } 42 } 43 int l=vec.size(); 44 for(int i=0;i<l-1;i++) 45 cout<<vec[i]<<" "; 46 cout<<vec[l-1]<<endl; 47 } 48 49 int main() 50 { 51 int n; 52 cin>>n; 53 for(int i=1;i<=n;i++) 54 cin>>beh[i]; 55 for(int i=1;i<=n;i++) 56 cin>>mid[i]; 57 build(1,n,1,n);//建树 58 bfs(beh[n]); 59 }