L2-011 玩转二叉树 （25 分)
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
int data;
struct node*l;
struct node*r;
}tree;
tree* creat1(int xian[],int zhong[] ,int len)
{
if(len<=0)
return NULL;
tree*head = new tree;
head->data = *xian;
int i = 0;
for(;i<len;i++)
{
if(zhong[i]==*xian)
{
break;
}
}
head->l = creat1(xian+1,zhong,i);
head->r = creat1(xian+i+1,zhong+i+1,len-i-1);
return head;
}
void ccout(tree*root)
{
queue<tree*>q;
tree*p =NULL;
if(root)
{
q.push(root);
}
int top = 1;
while(!q.empty())
{
p = q.front();
q.pop();
if(top)top =0;
else printf(" ");
cout<<p->data;
if(p->l)
{
q.push(p->l);
}
if(p->r)
{
q.push(p->r);
}
}
}
void Swap(tree*root)
{
if(!root) return ;
Swap(root->l);
Swap(root->r);
swap(root->l,root->r);
}
int main()
{
int n;
cin>>n;
int xian[36],zhong[36];
for(int i=0;i<n;i++)
{
cin>>zhong[i];
}
for(int i=0;i<n;i++)
{
cin>>xian[i];
}
tree*root = new tree;
root = creat1(xian,zhong,n);
Swap(root);
ccout(root);
return 0;
}