团体程序设计天梯赛-练习集L2-006. 树的遍历

L2-006. 树的遍历

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数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<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 1000
 4 int be[maxn],mid[maxn];
 5 struct Node
 6 {
 7     int l;
 8     int r;
 9 } aa[maxn];
10 //先从后序遍历中找到根节点，再到中序遍历找到它出现的位置，然后递归下去 
11 int build(int la,int ra,int lb,int rb)
12 {
13     if(la>ra)
14         return 0;//防止出界 
15     int root,p1,p2;
16     root=be[rb];
17     p1=la;
18     while(mid[p1]!=root) p1++;
19     p2=p1-la;
20     aa[root].l=build(la,p1-1,lb,lb+p2-1);//递归思想 
21     aa[root].r=build(p1+1,ra,lb+p2,rb-1);
22     return root;
23 }
24 void bfs(int x) //层次遍历
25 {
26     queue<int> q;
27     vector<int> v;
28     q.push(x);
29     while(!q.empty())
30     {
31         int w=q.front();
32         q.pop();
33         if(w==0)
34             break;
35         v.push_back(w);
36         if(aa[w].l!=0) q.push(aa[w].l);
37         if(aa[w].r!=0) q.push(aa[w].r);
38     }
39     int len=v.size();
40     for(int i=0; i<len; i++)
41         printf("%d%c",v[i],i==len-1?'
':' ');
42     return ;
43 }
44 int main()
45 {
46     int n;
47     scanf("%d",&n);
48     for(int i=0; i<n; i++) scanf("%d",&be[i]);
49     for(int i=0; i<n; i++) scanf("%d",&mid[i]);
50     build(0,n-1,0,n-1);
51     int root=be[n-1];
52     bfs(root);
53     return 0;
54 }

我会一直在