一、问题描述

注意可以假设数组中没有重复元素，这位我们判断子树是否为空时提供了便利。

二、DVC++版本

先是在DVEC++上编译的，供读者参考。
后面有LeetCode版的。

BiTree Resume_BiTree(TElemType *pre,TElemType *mid,int prelen,int midlen)
//6-65 前序序列和中序序列求出二叉树 
{BiTree want;if(! (want=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);if(prelen==0&&midlen==0)return NULL;want->data=pre[0];int rootposition=0;if(pre[0]==mid[0])want->lchild=NULL;else{rootposition=SearchNum(want->data,mid,midlen);want->lchild=Resume_BiTree(pre+1,mid,rootposition,rootposition);}if(pre[0]==mid[midlen-1])want->rchild=NULL;else{want->rchild=Resume_BiTree(pre+rootposition+1,mid+rootposition+1,prelen-rootposition-1,midlen-rootposition-1);}return want;	
} 

三、LeetCode版本

可以在LeetCode平台上直接运行。时间和空间复杂度都还不错。

代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int SearchNum(int num,int *array,int length)
{for(int i=0; i<length; i++)if(array[i] == num)return i;return -1;//没有找到。
}struct TreeNode* buildTree(int* pre, int prelen, int* mid, int midlen)
{struct TreeNode* want;want=(struct TreeNode*)malloc(sizeof(struct TreeNode));if(prelen==0&&midlen==0)return NULL;want->val=pre[0];int rootposition=0;if(pre[0]==mid[0])want->left=NULL;else{rootposition=SearchNum(want->val,mid,midlen);want->left=buildTree(pre+1,rootposition,mid,rootposition);}if(pre[0]==mid[midlen-1])want->right=NULL;else{want->right=buildTree(pre+rootposition+1,prelen-rootposition-1,mid+rootposition+1,midlen-rootposition-1);}return want;	
}