欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal

程序员文章站 2022-06-18 17:42:07
...

Construct Binary Tree from Preorder and Inorder Traversal

今天这题有些收获,这题给出的两个遍历结果分别是前序遍历和中序遍历,我一开始理解成了层序遍历和中序遍历,因为这个样例层序遍历与中序遍历的结果正好是一样的,最溜的是我最后写出来的理解成层序遍历的代码居然还跑过了!虽然时间上就很差。

这题的思路就是生成树,每次生成一个节点,我们知道前序遍历的第一个节点就是根节点,如果利用递归根节点其实是最先开始最后结束的一环,每次在递归函数内生成左右孩子。有了这样一个模糊的思路之后,下面我们需要每次选择正确的数字作为上一节点的左右孩子。

选择数字的规律如下:

在一定范围内,在前序遍历(preorder)的集合中,第i+1节点就是第i节点的左孩子

找出inorder中序遍历集合中值为preorder[i]的项,这个项的位置是count

超过这个count的下一个节点为第i节点的右孩子

leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal

以preorder=[5,3,2,1,4,7,6,8]

    inorder=[1,2,3,4,5,6,7,8]

为例 初始范围为所有

一开始 5 为根节点,对于inorder [1,2,3,45  ,6,7,8] //红色部分为左孩子,绿色为右孩子

再看preorder,第i+1节点为第i节点的左孩子,即3是5的左孩子,

count = 5

所以inorder中第6项 7是5的右孩子

进入左孩子的递归后,5的位置就相当于是1234的右边界

进入右孩子的递归,5的位置就相当于是678的左边界。


先上搞对题意之后最先写出的代码吧:

class Solution {
public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		if (preorder.empty()) return nullptr;
		//if(preorder.front()!=inorder.front()) has left child
		return gen_next(preorder, inorder, 0,preorder.size()-1, 0, preorder.size()-1);
	}
	TreeNode* gen_next(vector<int> preorder, vector<int> inorder, int pl,int pr,int l,int r)
	{
		if (pl > pr) return nullptr;
		TreeNode *now = new TreeNode(preorder[pl]);
		int count = 0;
		while (preorder[pl] != inorder[l+count]) count++;
		now->left = gen_next(preorder, inorder, pl+1,pl+count, l, l + count-1);
		now->right = gen_next(preorder, inorder, pl+count+1,pr, l + count+1, r);
		return now;
	}
};

这个代码跑了86ms,真的惊了,感觉似乎没什么毛病,这时间也忒长了。

后来思考了一下是不是在递归体内的循环花时间太多?

如果是的话,可以选择引入hash,这样可以把递归体内的那个while语句变成O(1)时间

代码如下:

class Solution {
public:
	unordered_map<int, int> map;
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		if (preorder.empty()) return nullptr;
		for (int i = 0; i < preorder.size(); i++)
		{
			map[inorder[i]] = i;
		}
		return gen_next(preorder,  0,preorder.size()-1,0);
	}
	TreeNode* gen_next(vector<int> preorder,int pl,int pr,int l)
	{
		if (pl > pr) return nullptr;
		TreeNode *now = new TreeNode(preorder[pl]);
		int count = map[preorder[pl]]-l;
		now->left = gen_next(preorder, pl+1,pl+count,l);
		now->right = gen_next(preorder, pl+count+1,pr,count+l+1);
		return now;
	}
};

44ms,感觉没有从根本上解决问题,也就是说某些地方还是花了更大的时间,

最后我发现,递归的参数中的vector最好变成传递指针也就是从 vector<int> 变成 vector<int> &

否则相当于每次递归都重新赋值了一个新向量,这个时间,啧啧啧..

最终版:12ms

class Solution {
public:
	unordered_map<int, int> map;
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		if (preorder.empty()) return nullptr;
		for (int i = 0; i < preorder.size(); i++)
		{
			map[inorder[i]] = i;
		}
		return gen_next(preorder,  0,preorder.size()-1,0);
	}
	TreeNode* gen_next(vector<int> &preorder,int pl,int pr,int l)
	{
		if (pl > pr) return nullptr;
		TreeNode *now = new TreeNode(preorder[pl]);
		int count = map[preorder[pl]]-l;
		now->left = gen_next(preorder, pl+1,pl+count,l);
		now->right = gen_next(preorder, pl+count+1,pr,count+l+1);
		return now;
	}
};