学步园

已知前序和中序遍历顺序构建二叉树的代码如下：

BinaryTreeNode *Construct(int *preorder, int *inorder, int length)
{
	if (preorder == NULL || inorder == NULL || length <= 0)
		return NULL;
	return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}
BinaryTreeNode *ConstructCore(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder)
{
	int rootValue = startPreorder[0];
	BinaryTreeNode *root = new BinaryTreeNode();
	root->value = rootValue;
	root->lchild = root->rchild = NULL;
	if (startPreorder == endPreorder)
	{
		if (startInorder == endInorder && *startPreorder == *startInorder)
			return root;
		else
			throw std::exception("Invalid input.");
	}
	int *rootInorder = startInorder;
	while (rootInorder <= endInorder && *rootInorder != rootValue)
		++rootInorder;
	if (rootInorder == endInorder && *rootInorder != rootValue)
		throw std::exception("Invalid input.");

	int lefLength = rootInorder - startInorder;
	int *leftPreOrderEnd = startPreorder + lefLength;
	if (lefLength > 0)
		root->lchild = ConstructCore(startPreorder + 1, leftPreOrderEnd, startInorder, rootInorder - 1);
	if (lefLength < endPreorder - startPreorder)
		root->rchild = ConstructCore(leftPreOrderEnd + 1, endPreorder, rootInorder + 1, endInorder);
	return root;
}