如何通过中序和层序序列建立二叉树

有这样一棵二叉树

根据节点个数 9 

层序遍历结果 15 23 8 16 2 32 28 7 11

中序遍历结果 16 23 7 32 11 2 28 15 8

预期先序输出 15 23 16 2 32 7 11 28 8 

运行结果

这个过程和建立二叉查找树(BST)的过程是非常相像的，将laSq[laIndex]插入到根为root的子树中，如果当前根节点为空，就是要新建结点的位置，如果不为空，根据二者的值在中序序列中的排序，选择将laSq[laIndex]插入到左子树/右子树中。

注意&不可缺少。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<set>
#include<string>
#include<tr1/unordered_map>using namespace std;
using namespace std::tr1;
typedef long long LL;const int maxn = 10007;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;int laSq[maxn],inSq[maxn];
int pos[maxn];//记录数值在中序序列中的位置 struct Node{int v;Node *lchild,*rchild;
};void insert(int laIndex,Node* &root){if(root==NULL){root = new Node;root->v = laSq[laIndex];root->lchild = root->rchild = NULL;return;}if(pos[root->v]<pos[laSq[laIndex]])insert(laIndex,root->rchild);else insert(laIndex,root->lchild);
}int n;void DFS(Node* root){if(root==NULL)return;printf("%d%s",root->v,root->v==inSq[n-1]?"
":" ");if(root->lchild!=NULL)DFS(root->lchild);if(root->rchild!=NULL)DFS(root->rchild);
}int main(){cin>>n;for(int i=0;i<n;i++){cin>>laSq[i];}for(int i=0;i<n;i++){cin>>inSq[i];pos[inSq[i]] = i;}Node* root = NULL;for(int i=0;i<n;i++)insert(i,root);DFS(root);return 0;
}

参考

根据中序和层序建立二叉树