力扣

力扣

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

限制：0 <= 节点个数 <= 5000

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

思路

前序遍历：根左右。中序遍历：左根右。所以对于前序遍历。一开始一定是二叉树的根——3。接着看中序，3的左边一定是左子树。因此划分出根3左子树9右子树20 15 7。接着对左右子树重复上述动作。

对于主函数，需要构建一个哈希表。作用是从先序遍历获取到根节点后，可以快速定位其在中序遍历数组中的位置。

再写一个构造函数。输入是vector<int>& preorder, vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)。

内部先写递归终止条件。接着寻找左右子树边界，接着构建新的根节点指针。分好左右子树后进行递归。

答案

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm> //标准算法的头文件
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

void preOrder(TreeNode* node) { //前序遍历
	if (!node)
		return;
	cout << node->val << endl;
	preOrder(node->left);
	preOrder(node->right);
}
void inOrder(TreeNode* node) { //中序遍历
	if (!node)
		return;
	inOrder(node->left);
	cout << node->val << endl;
	inOrder(node->right);
}

class Solution {
public:
	map<int, int> index; 
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		int n = preorder.size();
		//哈希 帮助快速在中序遍历数组中定位根节点
		for (int i = 0; i < n; i++)
			index[inorder[i]] = i;
		return construct(preorder, inorder, 0, n - 1, 0, n - 1);
	}
	TreeNode* construct(vector<int>& preorder, vector<int>& inorder,
		int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
		if (preorder_left > preorder_right)
			return nullptr;
		int preorder_root = preorder_left; //先序遍历的头就是根
		int inorder_root = index[preorder[preorder_root]]; //在中序遍历中定位
		TreeNode*root=new TreeNode(preorder[preorder_root]);  //构建根节点
		int size_left_tree= inorder_root - inorder_left; //获取左子树数目
		// 递归地构造左子树，并连接到根节点
		// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
		root->left = construct(preorder, inorder, preorder_left + 1, preorder_left + size_left_tree, inorder_left, inorder_root - 1);
		// 递归地构造右子树，并连接到根节点
		// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
		root->right = construct(preorder, inorder, preorder_left + size_left_tree + 1, preorder_right, inorder_root + 1, inorder_right);
		return root;
	}
};

void test02() {
	vector<int> preorder = { 1,2,4,7,3,5,6,8 };
	vector<int> inorder = { 4,7,2,1,5,3,8,6 };
	Solution solution;
	TreeNode* ret = solution.buildTree(preorder, inorder);
	preOrder(ret);
	inOrder(ret);
}

int main() {
	test02();
	system("pause");
	return 0;
}