重建二叉树

这道题的题目为：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

本文有关二叉树的结构体以及结点创建如下：

typedef int  DataType;

typedef struct  BSTreeNode{
	DataType data;
	struct BSTreeNode *left;
	struct BSTreeNode *right;
} BSTreeNode;

BSTreeNode *CreateNode(int data)
{
	BSTreeNode *node = (BSTreeNode *)malloc(sizeof(BSTreeNode));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

解题思路为：

例如分别输入一个二叉树的前序遍历序列[ 1, 2, 4, 7, 3, 5 ,6, 8]和中序遍历序列
[ 4, 7, 2, 1, 5, 3, 8, 6]。

根据前序遍历“根左右”的方法可知，1就是这棵二叉树的根结点。观察中序遍历序列确定根结点1的位置，由此可以得知中序遍历序列中根结点1左边的序列为二叉树左子树的中序遍历，有3个结点，左子树对应的前序遍历序列为[ 2, 4, 7]。同理可以得出二叉树右子树有4个结点，前序遍历序列[ 3, 5 ,6, 8]和中序遍历序列[ 5, 3, 8, 6]。如下图：

当分别确定了左右子树的前序和后序遍历序列，可以以同样的方法递归创建左右子树即可。

代码如下：

BSTreeNode * ConstructTree(int * startPreorder, int * endPreorder, int * startInorder, int *endInorder)
{
	//前序遍历的第一个元素，即为根节点
	int rootValue = startPreorder[0];
	//构建根结点
	BSTreeNode *root = CreateNode(rootValue);
	if (startPreorder == endPreorder)
	{
		if (startInorder == endInorder&&*startPreorder == *startInorder)
		{
			return root;
		}
		else
		{
			printf("invalid input!\n");
		}
	}
	//根据前序遍历中的根节点的值，在中序遍历中找到根节点
	int * rootInorder = startInorder;
	while (rootInorder <= endInorder&&*rootInorder != rootValue)
		++rootInorder;
	if (rootInorder == endInorder&&*rootInorder != rootValue)
	{
		printf("invalid input!\n");
	}
	//在中序数组中找到它的左子树的长度
	int leftLength = rootInorder - startInorder;
	//根据中序遍历中左子树的长度在前序遍历中找到左子树的位置
	int *leftPreorderEnd = startPreorder + leftLength;
	//创建左子树
	if (leftLength > 0)
	{
	
		root->left = ConstructTree(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
	}
	//创建右子树
	if (leftLength < endPreorder - startPreorder)
	{
		root->right = ConstructTree(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
	}
	return root;
}
BSTreeNode * Construst(int * preorder, int *inorder, int length)
{
	if (preorder == NULL || inorder == NULL || length <= 0)
		return NULL;
	return ConstructTree(preorder, preorder + length - 1, inorder, inorder + length - 1);
}