【回复加米】求问这题时间复杂度

这是蠡口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;
    }
}

两种都是n^2，没区别，都是从上到下，对于每个subtree，判断是不是bst并且求size

huali0415 发表于 2021-09-15 07:34:11
两种都是n^2，没区别，都是从上到下，对于每个subtree，判断是不是bst并且求size

但第一种速度会快很多 0ms 超过100%那种
第二种就慢

zhany 发表于 2021-09-15 09:04:11
但第一种速度会快很多 0ms 超过100%那种
第二种就慢

那是实际运行速度，理论复杂度就是n^2😄