13 lines in Java, 2ms solution. without global variable and new class


  • 0

    while the complexity may be large as O(n^2)? I am not that sure about it.
    use two helper, one to check if the subtree is BST, another one to get the size of the tree.
    maybe we can refine by combining them together :)

        public int largestBSTSubtree(TreeNode root) {
            if (root == null) {return 0;}
            if (isBST(root, null, null)) {return getSize(root);}
            return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
        }
        public boolean isBST(TreeNode root, Integer min, Integer max) {
            if (root == null) {return true;}
            return (min == null || root.val > min) && (max == null || root.val < max) && isBST(root.left, min, root.val) && isBST(root.right, root.val, max); 
        }
        public int getSize(TreeNode root) {
            if (root == null) {return 0;}
            return 1 + getSize(root.left) + getSize(root.right);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.