Joyce' Blog
0%

rebuild-bintree

发表于 更新于

题目描述

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

题解

明明都知道要用递归来建左子树和右子树，却一直写不对递归的参数。唉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode * makeTree(vector<int>& preorder, vector<int>& inorder, int index, int left, int right)
{
	if (left > right)return nullptr;
	TreeNode* root = new TreeNode(preorder[index]);
	if (left == right)return root;
	int i = left;
	while (inorder[i] != preorder[index])i++;
	root->left = makeTree(preorder, inorder, index + 1, left, i - 1);
	root->right = makeTree(preorder, inorder, index + i - left + 1, i + 1, right);
	return root;
}

TreeNode * buildTree(vector<int>& preorder, vector<int>& inorder) {
	int right = inorder.size();
	if (!right)return nullptr;
	return makeTree(preorder, inorder, 0, 0, right-1);
}

注意什么时候返回nullptr。