leetcode 110. 平衡二叉树

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上反复提交了几次,发现优化后的代码反而更慢了。请老师指点。

正在回答

登陆购买课程后可参与讨论,去登陆

1回答

最直接的原因是,这个问题的数据规模不够大,使得 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积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2618    人
  • 解答问题       1104    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
微信客服

购课补贴
联系客服咨询优惠详情

帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

公众号

扫描二维码
关注慕课网微信公众号

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师
插入代码