用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树， 输出新二叉树按先序遍历得到的结果。 提交格式：实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。 函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000，树的深度<=2000。 请不要printf输出任何内容。 输入样例1： n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5} 输出样例1： outOrder={1,5,2,4,3}

先序遍历和中序遍历是两种常见的遍历二叉树的方式。

先序遍历：先访问根结点，再依次遍历左子树和右子树。

中序遍历：先遍历左子树，再访问根结点，最后遍历右子树。

使用先序遍历和中序遍历可以构建二叉树，因为先序遍历的第一个结点一定是二叉树的根结点，中序遍历的根结点左边的结点一定是左子树，右边的结点一定是右子树。

对于给定的先序序列和中序序列，我们可以使用递归的方法来构建二叉树。假设当前要构建的二叉树的先序序列为preOrder[startPre...endPre]，中序序列为inOrder[startIn...endIn]，则可以按照如下步骤构建二叉树：

1. 在中序序列中找到根结点的位置，记为rootIn。
2. 则在先序序列中，根结点的位置就是startPre。
3. 因此左子树的先序序列为preOrder[startPre+1...startPre+rootIn-startIn]，中序序列为inOrder[startIn...rootIn-1]。
4. 右子树的先序序列为preOrder[startPre+rootIn-startIn+1...endPre]，中序序列为inOrder[rootIn+1...endIn]。
5. 递归构建左子树和右子树。

下面是使用先序序列和中序序列构建二叉树的代码