【21】重建二叉树

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

分析：

1. 在二叉树的前序序列中，第一个数总是二叉树的根结点的值。对应的如果把根节点的值在中序序列中找出来，则中序序列中位于根节点值的左边区间为左子树，右边为右子树

2. 根据题目假设的输入的两个序列是不重复的，因此我们可以利用扫描中序序列找到根节点，然后递归的建立二叉树即可

3. 利用一个BuildTree函数来返回BinaryTreeNode*，在函数内部利用new动态分配结点的内存，这样就不用担心函数返回栈区中分配的空间而使指针失效

//二叉树的结点
struct BinaryTreeNode{
    int value;
	BinaryTreeNode *lson;
	BinaryTreeNode *rson;
};

//重建二叉树
BinaryTreeNode* BuildTree(int *preOrder, int *inOrder, int n){
	//不合法的数据
	if(preOrder == NULL || inOrder == NULL || n <= 0){
	   return NULL;
	}
	BinaryTreeNode *root = new BinaryTreeNode();
	root->value = preOrder[0];
	root->lson = NULL;
	root->rson = NULL;
	//找到中序遍历中根节点的位置
	int index = 0;
	while(index < n && preOrder[0] != inOrder[index]){
	    ++index;
	}
	//不合法数据
	if(index >= n){
	    return NULL;
	}
	root->lson = BuildTree(preOrder+1, inOrder, index);
	root->rson = BuildTree(preOrder+1+index, inOrder+index+1, n-index-1);
	return root;
}