Clean and easy to understand Java Solution


  • 20
    H
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (isValid(root, null, null)) return countNode(root);
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    
    public boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min != null && min >= root.val) return false;
        if (max != null && max <= root.val) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
    
    public int countNode(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return 1 + countNode(root.left) + countNode(root.right);
    }

  • 3
    L

    Great Solution!

    A slight improvement: Line 3 of the code is unnecessary. In the case that there is only 1 node, count(n) will return the correct value of 1.

    Also, It is not necessary to pass in nulls for the Max and Min either. Just start off with Integer.MAX_VALUE and Integer.MIN_VALUE. This will save you extra checks in your isValid() method.

    Posting a slightly improved AC'ed solution:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
       
       public int largestBSTSubtree(TreeNode root) {
           if(root == null) return 0;
           if(isValid(root, Integer.MAX_VALUE, Integer.MIN_VALUE)) return count(root);
           else return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
       }
        
       public int count (TreeNode n){
           if(n == null)
               return 0;
           return 1 + count(n.left) + count(n.right);
       }
       
       public boolean isValid(TreeNode n, int max, int min){
           if(n == null) return true;
           if(n.val < max && n.val > min) return isValid(n.left, n.val, min) && isValid(n.right, max, n.val);
           else return false;
       }
       
    }

  • 12
    D

    As analyzed on Geeksforgeeks, this will result in a O(n^2) performance. Please make a note so people will not misinterpret this solution.


  • 2
    E
    public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        int ret = isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        if(ret >= 0){
            return ret;
        }
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    private int isValidBST(TreeNode node, int min, int max){
        if(node == null){
            return 0;
        }
        if(node.val < min || node.val > max){
            return -1;
        }
        int left = isValidBST(node.left, min, node.val);
        int right = isValidBST(node.right, node.val, max);
        return (left >= 0 && right >= 0)? left + right + 1 : -1;
    }
    

    }


  • 0
    L

    @ericxliu What is the time complexity of your solution?


  • 0
    W

    @limestone Here is a discussion on it. O(nlogn) Java solution


  • 0
    Z

    @danchen said in Clean and easy to understand Java Solution:

    misinterpret

    Yeah. I agree with you. Every node are traversed more than one time. It is not O(n).


  • 1
    Z

    @hollysinka This is definitely not O(n) solution. Please mark the complexity in the title, in order to make people not confused. For every node, you did isValid() and count() for it. This means for every node, you traverse all the nodes belong to this node, which is O(n). That is to say, you did O(n) for each node. So, when you finished the calculation, you did O(n) * n = O(n^2).


Log in to reply
 

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