leetcode 110. 平衡二叉树
bobo老师,这道题我优化后的代码反而更慢了,不太理解。未优化的代码如下:
class Solution {
private:
int height(TreeNode* node) {
if(node == nullptr) return 0;
return max(height(node->left), height(node->right)) + 1;
}
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
return abs(height(root->left) - height(root->right)) <= 1 &&
isBalanced(root->left) && isBalanced(root->right);
}
};
然后我考虑递归计算高度的时候,会有重复,于是优化了一下,代码如下:
class Solution {
private:
unordered_map<TreeNode*, int> hashMap;
int height(TreeNode* node) {
if(node == nullptr) return 0;
if(hashMap.find(node) != hashMap.end()) {
return hashMap[node];
}
int retHeight = max(height(node->left), height(node->right)) + 1;
hashMap[node] = retHeight;
return retHeight;
}
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
return abs(height(root->left) - height(root->right)) <= 1 &&
isBalanced(root->left) && isBalanced(root->right);
}
};
就是把计算过的节点高度保存一下,但是在leetcode上反复提交了几次,发现优化后的代码反而更慢了。请老师指点。
正在回答
最直接的原因是,这个问题的数据规模不够大,使得 O(n^2) 的算法不但能通过,还能比 O(n) 更快。如果这个问题的数据规模在 10^5 这个级别,不可能出现这种情况。
小数据量的情况下,O(n^2) 的算法可能是一种优化,因为常数低,请回顾在这个课程中,我们介绍的快排或者归并排序中,当数据范围小到一定程度的时候,我们反而可以使用插入排序这类 O(n^2) 的排序算法进行优化。
==========
次直接的原因,是哈希表实际上性能不高。虽然哈希表的时间复杂度是 O(1) 的,但这是理论上的时间复杂度,实际上,对于每次操作,计算哈希值,解决哈希冲突,包括可能的扩容等操作,都使得在小数据量,甚至是中等数据量上,哈希表示没有性能优势的。我甚至遇到过使用 unordered_map 超时,使用 map 能通过的情况。
if(hashMap.find(node) != hashMap.end()) 这是一次哈希表的查找,对于每次调用 height 都会执行;
return hashMap[node]; 这又是一次哈希表的查找
hashMap[node] = retHeight; 这是一次哈希表的插入
在小数据量的情况下,这些操作的性能损耗,是大于预存结果获得的性能提升的。
但是这个代码写的没有毛病,是很标准的记忆化搜索:)
继续加油!:)
相似问题
登录后可查看更多问答,登录/注册
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧