L2-011. 玩转二叉树

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

输入格式：

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

输出格式：

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

输入样例：

71 2 3 4 5 6 74 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2 思路：跟树的遍历一样

1 #include
      
        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
       
         q;23     vector
        
          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
         
          >n;41     for(int i=0;i
          
           >m[i];42     for(int i=0;i
           
            >f[i];43 build(0,n-1,0,n-1);44 int root=f[0];45 bfs(root);46 return 0;47 }