Joyce' Blog
0%

construct-binary-tree-from-preorder-and-inorder-traversal

发表于

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

题解

关键就是用前序遍历的数，将中序遍历分成两份，即左子树和右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1)
	{
		preorder.erase(preorder.begin());
		return new TreeNode(inorder[0]);
	}
	TreeNode* root = new TreeNode(preorder[0]);
	vector<int>left, right;
	int i = 0;
	for (; i < vsize; i++)
	{
		if (inorder[i] == preorder[0])
			break;
		else
			left.push_back(inorder[i]);
	}
	for (int j = i + 1; j < vsize; j++)
	{
		right.push_back(inorder[j]);
	}
	preorder.erase(preorder.begin());
	root->left = buildTree(preorder, left);
	root->right = buildTree(preorder, right);
	return root;
}

效率惨淡。主要因为每次递归前都重新创建了vector，再改改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode* subTree(int& index, int left, int right, vector<int>& preorder, vector<int>& inorder)
{
	if (left == right)return NULL;
	if (right - left == 1)
	{
		index++;
		return new TreeNode(inorder[left]);
	}
	TreeNode* root = new TreeNode(preorder[index]);
	int i = left;
	for (; i < right; i++)
	{
		if (inorder[i] == preorder[index])
			break;
	}
	index++;
	root->left = subTree(index, left, i, preorder, inorder);
	root->right = subTree(index, i + 1, right, preorder, inorder);
	return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1) return new TreeNode(inorder[0]);
	int i = 0;
	return subTree(i,0,vsize,preorder,inorder);
}

我明天就不刷题了哈，最近多爬点数据好交差~~