重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列

{4,7,2,1,5,3,8,6}，则重建出图所示的二叉树并输出它的头结点。二叉树结点的定义如下：

struct BinaryTreeNode

{

int data;

BinaryTreeNode* lchild;

BinaryTreeNode* rchild;

};

解析：在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

如图所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历的特点,在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的都是有右子树结点的值。

由于在中序遍历序列中，有3个数字是左子树结点的值,因此左子树共有3个左子结点。同样,在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到左右子树对应的子序列。

参考代码：

 1 BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder)
 2 {
 3     //前序遍历序列的第一个数字是根结点的值
 4     int rootValue=startPreorder[0];
 5     BinaryTreeNode* root=new BinaryTreeNode();
 6     root->data=rootValue;
 7     root->lchild=root->rchild=NULL;
 8 
 9     if(startPreorder==endPreorder)
10     {
11         if(startInorder==endInorder&&*startPreorder==*startInorder)
12             return root;
13         else
14             throw exception("Invalid input.");
15     }
16 
17     //在中序遍历中找到根结点的值
18     int* rootInorder=startInorder;
19     while(rootInorder <= endInorder&&*rootInorder!=rootValue)
20         ++rootInorder;
21     if(rootInorder==endInorder&&*rootInorder!=rootValue)
22         throw exception("Invalid input.");
23     int leftLength=rootInorder-startInorder;//中序遍历左子树长度
24     int* leftPreorderEnd=startPreorder+leftLength;
25     if(leftLength>0)
26     {
27         //构建左子树
28         root->lchild=ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
29     }
30     if(leftLength<endPreorder-startPreorder)
31     {
32         //构建右子树
33         root->rchild=ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
34     }
35     return root;
36 }
37 
38 BinaryTreeNode* Construct(int* preorder,int* inorder,int length)//由先序和中序重建二叉树
39 {
40     if(preorder==NULL||inorder==NULL||length<=0) return NULL;
41     return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);
42 }