leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
今天这题有些收获,这题给出的两个遍历结果分别是前序遍历和中序遍历,我一开始理解成了层序遍历和中序遍历,因为这个样例层序遍历与中序遍历的结果正好是一样的,最溜的是我最后写出来的理解成层序遍历的代码居然还跑过了!虽然时间上就很差。
这题的思路就是生成树,每次生成一个节点,我们知道前序遍历的第一个节点就是根节点,如果利用递归根节点其实是最先开始最后结束的一环,每次在递归函数内生成左右孩子。有了这样一个模糊的思路之后,下面我们需要每次选择正确的数字作为上一节点的左右孩子。
选择数字的规律如下:
在一定范围内,在前序遍历(preorder)的集合中,第i+1节点就是第i节点的左孩子
找出inorder中序遍历集合中值为preorder[i]的项,这个项的位置是count
超过这个count的下一个节点为第i节点的右孩子
以preorder=[5,3,2,1,4,7,6,8]
inorder=[1,2,3,4,5,6,7,8]
为例 初始范围为所有
一开始 5 为根节点,对于inorder [1,2,3,4, 5 ,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;
}
};
推荐阅读
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
LeetCode 94. Binary Tree Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal