## 7-75 玩转二叉树 (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
“`
“`cpp
#include<iostream>
#include<cstdio>
#include<malloc.h>
using namespace std;
struct node{
int data;
node *left;
node *right;
} *head;
typedef node* Node;
int n;
int a[35];//中序遍历
int b[35];//前序遍历
void insert(Node &p,Node &h){//插入结点,使用引用！！！
if(h==NULL){
h=p;
return ;
}
int ai,bi;
for(int i=0;i<n;i++){
if(a[i]==p->data){//待插入字符在中序遍历的位置
ai=i;
break;
}
}
for(int i=0;i<n;i++){
if(a[i]==h->data){//根节点字符在中序遍历的位置
bi=i;
break;
}
}
if(ai<bi){//在根节点左边
insert(p,h->left);
}
else{//在根节点右边
insert(p,h->right);
}
}
void create(){//建树
for(int i=0;i<n;i++){
Node p=(Node)malloc(sizeof(node));
p->data=b[i];
p->left=NULL;
p->right=NULL;
insert(p,head);
}
}
void swap(Node p){//交换左右结点
if(p==NULL){
return ;
}
else{
Node temp=p->left;
p->left=p->right;
p->right=temp;
swap(p->left);
swap(p->right);
}
}
int level(Node p,int cur){//求层数
if(p==NULL){
return cur;
}
else{
return max(level(p->left,cur+1),level(p->right,cur+1));
}
}
void lvorder(Node p,int cur,int pos){//层序遍历
if(p==NULL||cur>pos){
return ;
}
if(cur==pos){
if(pos!=0){
printf(” “);
}
printf(“%d”,p->data);
}
else{
lvorder(p->left,cur+1,pos);
lvorder(p->right,cur+1,pos);
}
}
int main(){
head=NULL;
scanf(“%d”,&n);
for(int i=0;i<n;i++){//读入中序遍历
scanf(“%d”,&a[i]);
}
for(int i=0;i<n;i++){//读入前序遍历
scanf(“%d”,&b[i]);
}
create();//建树
swap(head);//镜像反转
int l=level(head,0);//记录层数
for(int i=0;i<l;i++){//每层输出
lvorder(head,0,i);
}
return 0;
}
“`
本文出自：https://blog.csdn.net/ice_bear221/article/details/108045920