题目分析：
前序遍历的顺序是：根节点，左节点，右节点
中序遍历的顺序：左节点，根节点，右节点
假设前序遍历的顺序是：1 2 4 7 3 5 8 9 6
中序遍历的顺序是:4 7 2 1 8 5 9 3 6
1.根据前序遍历的规则，前序遍历的第一个节点一定是根节点。
2.从中序遍历中找到第1步根节点所在的位置，在中序序列中根节点所在位置的左边序列就是二叉树的左子树，右边序列就右子树。
3.假设第2步找到的根节点在中序序列中的第k个位置，那么在前序序列的第[2,k]位置的序列是二叉树的左子树，第[k+1,end]位置的序列是二叉树右子树的序列。
4.根据1,2,3的描述，递归生成左子树和右子树。
题目中最大节点数是1000，如果使用数组，考虑到单侧树，则数组至少需要2^1000的空间。所以使用链式结构存储二叉树的结构。
实现代码如下：
#include<stdio.h>
#include<malloc.h>
struct Node{
int data;
Node *lchild,*rchild;
Node(){
lchild=NULL;
rchild=NULL;
}
}node[1010];
int n,cnt;
int preorder[1010],inorder[1010];
Node *root=&node[0];
//清空左，右子树的指针
void init(){
int i;
for(i=0;i<2020;i++){
node[i].lchild=NULL;
node[i].rchild=NULL;
}
}
//根据前序和中序序列生成二叉树
void create(Node *temp,int prest,int preed,int inst,int ined){
int i;
if(prest>preed)return;
temp->data=preorder[prest];
if(prest==preed)return;
int index = -1;
//找到根节点在中序序列中的位置
for(i=inst;i<=ined;i++){
if(preorder[prest]==inorder[i]){
index=i;
break;
}
}
if(index==-1)return;
int distance=index-inst;
//只存在左子树的情况
if(index==inst){
temp->rchild=&node[cnt++];
create(temp->rchild,prest+1,preed,inst+1,ined);
}else if(index==ined){//只存在右子树的情况
temp->lchild=&node[cnt++];
create(temp->lchild,prest+1,preed,inst,ined-1);
}else{
//左右子树都存在
temp->rchild=&node[cnt++];
temp->lchild=&node[cnt++];
create(temp->lchild,prest+1,prest+distance,inst,index-1);
create(temp->rchild,prest+distance+1,preed,index+1,ined);
}
}
//打印二叉树后序遍历的序列
void print(Node *temp){
if(temp==NULL){
return;
}
print(temp->lchild);
print(temp->rchild);
printf("%d",temp->data);
if(temp!=root){
printf(" ");
}
}
int main(){
int i;
while(scanf("%d",&n)!=EOF){
cnt=1;
init();
//获得前序遍历序列
for(i=0;i<n;i++){
scanf("%d",&preorder[i]);
}
//获得中序遍历序列
for(i=0;i<n;i++){
scanf("%d",&inorder[i]);
}
create(root,0,n-1,0,n-1);
print(root);
printf("\n");
}
return 0;
}