先由前序和中序确定二叉树，然后再反转二叉树

（选做题）给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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）先序遍历中第一个是根那么在中序遍历中找到根那么左右子树就确定了，所以自然左右子树的范围就确定了，所以在递归方法中先序遍历的左子树的边界范围是l1 + 1, l1 + i - l2

因为第一个是根所以下一次递归的时候应该是下一个位置，但是左子树应该在什么位置结束呢？我们可以通过中序遍历中左子树的范围进行确定，可以结合上面的例子进行理解，可以知道左子树的范围为l1 + (i - l2)

也可以这样想设先序遍历左子树结束位置为x，则x + 1- (l1 + 1) = i - l2，所以可以得到左子树的结束范围是 l1 + (i - l2)，对于中序遍历序列中当前左子树的范围应该是l2, i - 1（i为根所在的位置）

2）对于右子树来说，我们知道前序遍历的范围的起点应该是在前序遍历左子树结束位置上加1的位置，结束位置是在r1, 中序遍历中右子树的范围应该是i + 1, r2

我们可以模仿之前的递归创建完全二叉树的例子，可以将根节点的左指针指向递归创建的左子树，根节点的右指针指向递归创建的右子树即可

3）核心是其中的递归方法中参数的确定

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElementType;
typedef struct BiTNode{
   
    ElementType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;
BiTree CreatBinTree(int *pre,int *in,int l1,int r1,int l2,int r2 );
void invertTree(BiTree root);
void LevelorderTraversal( BiTree BT );
int main()
{
   
        BiTree T;
	int prelist[1000];
	int inlist[1000];
	int length;
	/* 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7 */
	scanf("%d",&length);
	for(int i=0;i<length;i++)
	{
   
		scanf("%d",&inlist[i]);
	}
		for(int i=0;i<length;i++)
	{
   
		scanf("%d",&prelist[i]);
	}
	T=CreatBinTree(prelist,inlist, 0,length-1,0,length-1);//注意是（0,length-1） 
    invertTree(T);
    LevelorderTraversal(T);
    return 0;
}
void invertTree(BiTree root) {
   //反转
    if(root == NULL)
    return ;
    BiTree p = root;
    p = root->lchild;
    root->lchild= root->rchild;
    root->rchild = p;
    invertTree(root->lchild);
    invertTree(root->rchild);
}
void LevelorderTraversal( BiTree BT )
{
   
	BiTree p;
	BiTree q[1004];
	int head=0;int tail=0;
	if(BT)
	{
   
		q[tail++]=BT;
	while(head!=tail)
	{
   
		p=q[head++];
		printf(" %d",p->data);
		if(p->lchild)
		{
   
			q[tail++]=p->lchild;
		}
		if(p->rchild)
		{
   
			q[tail++]=p->rchild;
		}
	}
	}
}
BiTree CreatBinTree(int *pre,int *in,int l1,int r1,int l2,int r2 )
{
   
	if(l1>r1) return NULL;
	BiTree T;
	T=(BiTree)malloc(sizeof(BiTNode));
	T->data=pre[l1];
	int i;
	for(i=l2;i<r2;i++)
	{
   
		if(in[i]==pre[l1]) break;
	}
	T->lchild=CreatBinTree(pre, in, l1+1,l1+(i-l2),l2,i-1);
	T->rchild=CreatBinTree(pre, in, l1+(i-l2)+1,r1,i+1,r2);
	return T;
}