C++——从前序与中序遍历序列构造二叉树leetcode105

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

思路

来源于leetcode官方解答，先序遍历的排布是[根节点，左子树，右子树]，中序遍历的排布是[左子树，根节点，右子树]，因此，从先序第一个元素可以找到中序中的根节点的位置，从而可以确定出左子树和右子树的节点数目，从而可以正确划分这一级的先序遍历的左右子树，对于左右子树内部也是对应的排列方式，因此可以考虑迭代，每次更新先序遍历和中序遍历的左右边界。
同时为了减少每次查询中序根节点位置，可以考虑将值和索引使用哈希表存放。

代码

unordered_map<int, int> hash_map;
TreeNode* mybuildTree(vector<int> preorder, vector<int> inorder, int preorder_l, int preorder_r, int inorder_l, int inorder_r)
{
	if(preorder_l>preorder_r) return nullptr;
	int pos = hash_map[preorder[preorder_l]]; // 根节点在中序中的位置
	TreeNode* root = new TreeNode(preorder[preorder_l]);
	int left_tree_length = pos-inorder_l;
	int right_tree_length = inorder_r-pos;
	root->left = mybuildTree(preorder, inorder, preorder_l+1, preorder_l+left_tree_length, inorder_l, pos-1);
	root->right = mybuildTree(preorder, inorder, preorder_r-right_tree_length+1, preorder_r, pos+1, inorder_r);
	return root;
}
TreeNode* buildTree(vector<int> preorder, vector<int> inorder)
{
	int n = preorder.size();
	for(int i = 0; i<n; i++)
	{
		hash_map[inorder[i]] = i; // 值：索引
	}
	return mybuildTree(preorder, inorder, 0, n-1, 0, n-1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22