天梯赛L2-011. 玩转二叉树

L2-011. 玩转二叉树

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

根据前序、中序序列还原建树，然后镜面反转，就是将非叶子节点的左右孩子互换，最后层序遍历输出这棵树。

 1 #include<iostream>
 2 #include<queue>
 3 #define maxn 1000
 4 
 5 using namespace std;
 6 
 7 int n;
 8 int qian[1000],zh[1000];
 9 struct node
10 {
11     int l,r;
12 }pp[1000];
13 
14 int build(int la,int ra,int lb,int rb)
15 {
16     if(la>ra)
17         return 0;
18     int root,p1,p2;
19     root=qian[lb];
20     p1=la;
21     while(zh[p1]!=root)
22         p1++;
23     p2=p1-la;
24     pp[root].l=build(la,p1-1,lb+1,lb+p2-1);
25     pp[root].r=build(p1+1,ra,lb+p2+1,rb);
26     return root;
27 }
28 void fan(int root)
29 {
30     if(pp[root].l || pp[root].r)
31     {
32         int temp = pp[root].l;
33         pp[root].l = pp[root].r;
34         pp[root].r = temp;
35         if(pp[root].l)
36             fan(pp[root].l);
37         if(pp[root].r)
38             fan(pp[root].r);
39     }
40 }
41 void level()
42 {
43     queue<int>q;
44     q.push(qian[0]);
45     cout<<qian[0];
46     while(!q.empty())
47     {
48         int temp = q.front();
49         q.pop();
50         if(temp!=qian[0])
51             cout<<' '<<temp;
52         if(pp[temp].l)
53             q.push(pp[temp].l);
54         if(pp[temp].r)
55             q.push(pp[temp].r);
56     }
57     cout<<endl;
58 }
59 int main()
60 {
61     scanf("%d",&n);
62     for(int i = 0; i < n; i++)
63         cin>>zh[i];
64     for(int i = 0; i < n; i++)
65         cin>>qian[i];
66     build(0,n-1,0,n-1);
67     fan(qian[0]);
68     level();
69     return 0;
70 }