由二叉树的中序层序重建二叉树
writer：pprp
用层序中序来重建二叉树
其实本质上与前序中序建立二叉树没有什么太大区别
大概思路：
递归解法，对当前层进行处理，通过层序遍历可以得到当前的根节点，然后在中序遍历中找到该节点，对左右两边的内容进行分析，理想情况下应该是可以递归进行下去，找到左子树的中序遍历和层序遍历，找到右子树的中序遍历和层序遍历，然后进行递归，但是可以发现，层序遍历是交错的，所以是需要重新处理以后才能进行递归
现在只要通过处理得到左子树右子树的层序遍历序列就好了，通过两层循环找到在左子树中出现的元素在层序遍历中出现的顺序，并将其存储在新开的数组中，然后就可以继续递归下去了
代码如下：
#include#include #include #include using namespace std;const int maxn = 10000;struct tree{ tree * l, *r; int data; tree() { l = r = NULL; data = 0; }};int layer[maxn], in[maxn];//前序遍历void PreOrder(tree * root){ if(root != NULL) { cout << root->data << " "; PreOrder(root->l); PreOrder(root->r); }}//后序遍历void PostOrder(tree * root){ if(root != NULL) { PostOrder(root->l); PostOrder(root->r); cout << root->data << " "; }}//从 0 开始tree * CreateTree(int * layer, int * in, int t){ if(t == 0) return NULL; int Llayer[maxn], Rlayer[maxn]; int Lin[maxn], Rin[maxn]; tree * node = new tree; node->data = layer[0]; //find the place of the root int i; for(i = 0; i < t; i++) if(in[i] == layer[0]) break; //in order int cnt = 0; for(int j = 0; j < i ; j++) Lin[cnt++] = in[j]; cnt = 0; for(int j = i+1; j < t; j++) Rin[cnt++] = in[j]; cnt--; //layer order int Llayercnt = 0; int Rlayercnt = 0; for(int j = 1; j < t ; j++) for(int k = 0 ; k < i ; k++) if(layer[j] == in[k]) Llayer[Llayercnt++] = layer[j]; for(int j = 1; j < t; j++) for(int k = i ; k < t; k++) if(layer[j] == in[k]) Rlayer[Rlayercnt++] = layer[j]; node->l = CreateTree(Llayer,Lin,Llayercnt); node->r = CreateTree(Rlayer,Rin,Rlayercnt); return node;}int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++)cin >> layer[i]; for(int i = 0 ; i < n ; i++)cin >> in[i]; tree * root; root = CreateTree(layer,in,n); PreOrder(root); cout << endl; PostOrder(root); return 0;}