【剑指offer】重建二叉树

重建二叉树

---

题目描述

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

解题思路

1. 前序遍历的第一个结点是根结点（前序遍历：根-左-右，中序遍历：左-根-右）
2. 在中序遍历中找到根结点，则根结点的左侧是左子树，右侧是右子树
3. 在前序遍历中找到根结点的下一个结点则是对应下一层的根结点，此时再在中序遍历中该结点的左侧是左子树，右侧是右子树
4. 根据上述掌握的方法可利用递归的方法

实例说明
前序遍历序列{1,2,4,7,3,5,6,8}
中序遍历序列{4,7,2,1,5,3,8,6}

首先确定根结点及其位置

根据前序遍历与中序遍历的分析过程

最终得到的二叉树

代码实现

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;

	TreeNode(int x) :
		val(x), 
		left(NULL), 
		right(NULL)
	{

	}
};

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
	vector<int> leftPre;
	vector<int> rightPre;
	vector<int> leftVin;
	vector<int> rightVin;

	if (pre.size() <= 0 || vin.size() <= 0)
	{
		return nullptr;
	}

	TreeNode* root = new TreeNode(pre[0]);//前序遍历的第一个结点是根结点
	int rootPos = 0;
	for (int i = 0; i < vin.size(); i++)
	{
		if (pre[0] == vin[i])//找到中序遍历中根结点的位置
		{
			rootPos = i;
			break;
		}
	}

	for (int i = 0; i < rootPos; i++)
	{
		leftPre.push_back(pre[i + 1]);//先序遍历的根结点的下一个结点
		leftVin.push_back(vin[i]);
	}

	for (int j = rootPos + 1; j < vin.size(); j++)
	{
		rightPre.push_back(pre[j]);
		rightVin.push_back(vin[j]);
	}

	root->left = reConstructBinaryTree(leftPre, leftVin);
	root->right = reConstructBinaryTree(rightPre, rightVin);

	return root;
}