查看: 262|回复: 3
收起左侧

[树/链表/图] 【回复加米】求问这题时间复杂度

|只看干货
zhany | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (28)
 
 
3% (1)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
这是蠡口333(找最大的subtree)评论区的一个题解,想问下这个算法的复杂度是不是O(n),如果是的话为什么是呢,还有下面第二个解法是O(n^2),不明白这两个解法的区别。回复都加米!
解法1:
class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isBST(root)) return getCount(root);
        int L = largestBSTSubtree(root.left);
        int R = largestBSTSubtree(root.right);
        return Math.max(L, R);
    }
    private boolean isBST(TreeNode root) {
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    private boolean isBST(TreeNode root, int min, int max) {
        if (root == null) return true;
        return min < root.val && root.val < max && isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }
    private int getCount(TreeNode root) {
        if (root == null) return 0;
        return 1 + getCount(root.left) + getCount(root.right);
    }
}
解法2:
class Solution {
    int res = 0;
    double pre = -Double.MAX_VALUE; //Integer.MIN_VALUE也可以
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        pre = -Double.MAX_VALUE; //每轮更新一下
        if (isBST(root)) { //是BST了才更新一下res
           res =  Math.max(res, getCnt(root));
        }
        largestBSTSubtree(root.left);
        largestBSTSubtree(root.right);
        return res;
    }
    private int getCnt(TreeNode node) { //得到所有儿子数
        if (node == null) return 0;
        return getCnt(node.left) + getCnt(node.right) + 1;
    }
    private boolean isBST(TreeNode root) { //验证是不是BST的方法
        if (root == null) return true;
        boolean l = isBST(root.left);
        if (root.val <= pre) return false;
        pre = root.val;
        boolean r = isBST(root.right);
        return l && r;
    }
}

image.png

评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:拿到了knight badge开心
下一篇:LeetCode 学生99块又有了
huali0415 2021-9-15 22:34:11 来自APP | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   95% (139)
 
 
4% (6)    👎
两种都是n^2,没区别,都是从上到下,对于每个subtree,判断是不是bst并且求size

评分

参与人数 1大米 +1 收起 理由
zhany + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| zhany 2021-9-16 00:04:11 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (28)
 
 
3% (1)    👎
huali0415 发表于 2021-09-15 07:34:11
两种都是n^2,没区别,都是从上到下,对于每个subtree,判断是不是bst并且求size
但第一种速度会快很多 0ms 超过100%那种
第二种就慢
回复

使用道具 举报

huali0415 2021-9-16 00:33:02 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (139)
 
 
4% (6)    👎
zhany 发表于 2021-09-15 09:04:11
但第一种速度会快很多 0ms 超过100%那种
第二种就慢
那是实际运行速度,理论复杂度就是n^2😄

评分

参与人数 1大米 +1 收起 理由
zhany + 1 赞一个

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表