学习用品

重建二叉树

题目描述

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

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M

只是空行用

解题思路

以二叉树的创建为基础,依据中序序列的性质(根左边是左子树结点,根右边是右子树结点)进行递归。

不可以直接递归,需要额外的存储容器,否则将造成系统栈溢出。

只是空行用

代码

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
	int length = pre.size();
	if (length == 0) return NULL;

	//定位中序序列中根的位置
	int pos;
	for (int i = 0; i < length; i++)
	{
		if (pre[0] == vin[i])
		{
			pos = i;
			break;
		}
	}

	//创建根节点
	TreeNode* root = new TreeNode(pre[0]);

	//创建子树容器
	vector<int> pre_left, pre_right, vin_left, vin_right;

	//中序遍历中,左子树结点在根节点左侧,右子树同理
	//依靠此性质,对二叉树结点进行归并
	for (int i = 0; i < pos; i++)
	{
		pre_left.push_back(pre[i + 1]); //第一个数据为根节点
		vin_left.push_back(vin[i]);
	}
	for (int i = pos + 1; i < length; i++)
	{
		pre_right.push_back(pre[i]);
		vin_right.push_back(vin[i]);
	}

	//递归建树,直至叶节点
	root->left = reConstructBinaryTree(pre_left, vin_left);
	root->right = reConstructBinaryTree(pre_right, vin_right);
	return root;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注