登录
  • #刷题

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

zhany
166
3
这是蠡口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;

}

}
3条回复
热度排序

发表回复