例题-重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

原理

在前序遍历中，第一个数字是二叉树的根节点；

而在中序遍历中，根节点的左侧是左子树的节点，根节点的右侧是右子树的节点。

由此可以先从先序遍历中找到根节点，然后再遍历中序遍历找到其中根节点位置，以分割左右子树。

代码实现

class TreeNode
{
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree
{
public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
    {
    	// 递归出口
    	if (pre.empty() || vin.empty())
    		return nullptr;
    	// 建立根节点
    	TreeNode* head = new TreeNode(pre[0]);
    	// 查找中序遍历中根节点的索引值
    	int root = 0;
    	for (int i = 0; i < pre.size(); ++i)
    	{
    		if (vin[i] == pre[0])
    		{
    			root = i;
    			break;
    		}
    	}
    	// 先序遍历和中序遍历的左右子树vector
    	vector<int> pre_left, pre_right, vin_left, vin_right;
    	for (int i = 0; i < root; ++i) 
    	{
    		pre_left.push_back(pre[i + 1]);
    		vin_left.push_back(vin[i]);
    	}
    	for (int i = root + 1; i < pre.size(); ++i) 
    	{
    		pre_right.push_back(pre[i]);
    		vin_right.push_back(vin[i]);
    	}
    	// 根节点的左右节点
    	head->lchild = reConstructBinaryTree(pre_left, vin_left);
    	head->rchild = reConstructBinaryTree(pre_right, vin_right);
    	return head;
    }
};

例子1：

输入为

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

输出为

{1,2,5,3,4,6,7}

例子2

输入为

[1,2,4,5,3,6,7],[4,2,5,1,6,3,7]

输出为

{1,2,3,4,5,6,7}