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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

4 6 1 7 5 3 2

勉强敲出来了，包括已知中序和前序建树求层序遍历树的序列，虽然还有两组数据没有过，但是也够了。

O(∩_∩)O哈哈~

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int maxn = 35 ;int n, num;string a, b;typedef struct node{ int data ; struct node *lchild, *rchild;}*BiTree, BiNode;void Creat_Tree(BiTree & T, string a, string b){ if( b.length() == 0 ){ T = NULL ; return ; } char root_Node = b[0]; int index = a.find(b[0]); string l_a = a.substr(0,index); string r_a = a.substr(index+1); int l_len = l_a.length(); int r_len = r_a.length(); string l_b = b.substr(1,l_len); string r_b = b.substr(1+l_len); T = (BiTree)malloc(sizeof(BiNode)); if( T!=NULL){ T -> data = root_Node - 48 ; Creat_Tree(T->lchild, l_a, l_b); Creat_Tree(T->rchild, r_a, r_b); }}int main(){ BiTree T; cin >> n ; if( n == 0 ) return 0 ; for(int i=0; i
             
              > num ; a.push_back(num + '0'); } for(int i=0; i
              
               > num ; b.push_back(num+'0'); } Creat_Tree(T,a,b); queue
               
                 q; q.push(T); bool flag = true ; while( !q.empty() ){ BiTree m = q.front(); if( flag ){ cout << m->data ; flag = false ; } else{ cout << " " << m->data ; } if( m->rchild ) q.push(m->rchild); if( m->lchild ) q.push(m->lchild); q.pop(); } cout << endl ; return 0;}
               
              
             
            
           
          
         
        
       
      

 

加个正确的解答吧。完美AC的。

来源：

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=35;int n,cnt,root;int inod[MAXN],preod[MAXN];int q[35],head,tail;struct Node {    int lson,rson,num;}tr[MAXN];int dfs(int pl,int pr,int il,int ir) {    if(pl==pr) {        tr[cnt].lson=tr[cnt].rson=-1;        tr[cnt].num=preod[pl];        return cnt++;    }    for(int i=il;i<=ir;++i) {        if(preod[pl]==inod[i]) {            int cur=cnt++;            tr[cur].lson=tr[cur].rson=-1;            tr[cur].num=preod[pl];            if(il