Preface

学校码图的数据结构实验第二题，~~因为是码图所以可以随便欺负,所以不需要写很高效的算法应该也能过吧；~~ 抱着这样的想法就戳辣;

这题如果直接手搓一个二叉树链式结构来模拟会发现最多得到90分,所以多想一点点;

让我们开始吧！

Content

这里是题目:构造二叉树

用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树，输出新二叉树按先序遍历得到的结果。

提交格式：实现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}

由于先序遍历和中序遍历肯定能唯一确定一棵二叉树,所以我们不需要真的新建一棵二叉树;

回顾先序遍历的性质:先遍历左子树再遍历右子树，那么假设索引从到的子树应该是这样的结构：[ ] [ ,...,][ ,...,],其中作为子树根节点，作为的儿子;

我们找出和这棵子树在中序遍历的位置[...,,...][][...,,...],事实上可以确定左右子树的规模;

交换子树应该达到的效果是这样的(对于先序遍历数组): [ ] [ ,...,][ ,...,]; 我们递归地交换每个结点就可以做到;

~~说的有些抽象，可以写个测试用例多单步调试一下就明白了~~ 直接贴代码

#include<map>
std::map<int, int> pos;
int *SwapSon(int *a,int *res,int l,int r,int x,int y){
    if(l>r) return res;
    *res++=a[l];
    int m=pos[a[l]];
    res=SwapSon(a,res,r-y+m+1,r,m+1,y);
    res=SwapSon(a,res,l+1,l+m-x,x,m-1);
    return res;
}
void solve(int n, int *preOrder, int *inOrder, int *outOrder){
    for (int i=0;i<n;i++) pos[inOrder[i]]=i;
    SwapSon(preOrder,outOrder,0,n-1,0,n-1);
}