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<bits/stdc++.h> 2 using namespace std; 3 #define maxn 1000 4 struct Node{ 5 int l; 6 int r; 7 }aa[maxn]; 8 int f[maxn],m[maxn]; 9 int build(int la,int ra,int lb,int rb){ 10 if(la>ra) 11 return 0; 12 int root,p1,p2; 13 root=f[lb]; 14 p1=la; 15 while(m[p1]!=root) p1++; 16 p2=p1-la; 17 aa[root].l=build(la,p1-1,lb+1,lb+p2); 18 aa[root].r=build(p1+1,ra,lb+p2+1,rb); 19 return root; 20 } 21 void bfs(int root){ 22 queue<int> q; 23 vector<int> v; 24 q.push(root); 25 while(!q.empty()){ 26 int w=q.front(); 27 q.pop(); 28 if(w==0) 29 break; 30 v.push_back(w); 31 if(aa[w].r!=0) q.push(aa[w].r); 32 if(aa[w].l!=0) q.push(aa[w].l); 33 } 34 int len=v.size(); 35 for(int i=0;i<len;i++) 36 printf("%d%c",v[i],i==len-1?' ':' '); 37 } 38 int main(){ 39 int n; 40 cin>>n; 41 for(int i=0;i<n;i++) cin>>m[i]; 42 for(int i=0;i<n;i++) cin>>f[i]; 43 build(0,n-1,0,n-1); 44 int root=f[0]; 45 bfs(root); 46 return 0; 47 }