Simple Java Solution using Divide & Conquer


  • 2
    T

    Here I defined a class to save the information of each node, boolean b is for whether it is a BST, max is the max value of this BST, min is the min value of this BST, count means the number of nodes in this BST.

    If both its left node and right node are BST (l.b == true && r.b == true) AND the max value of left subtree less than node , the min value of right subtree greater than node, we can say it is a BST. (root.val > l.max && root.val < r.min). And the node number equals to the number of left node + the number of right node. (result.count = l.count + r.count + 1). Also, we need to update its max, min, and b

    Note: Since I used max_value and min_value in this solution, there should be potential bugs if the value of a leaf node is max_value / min_value. But this solution is accepted. Second edition is without using max_value and min_value, there are more conditions to judge.

    public class Solution {
    public class ResultType {
        boolean b;   /*a BST or not*/
        int max;   /* max value of this tree*/
        int min;   /*min value of this tree*/
        int count = -1;
    }
    public ResultType sub(TreeNode root) {
        ResultType result = new ResultType();
        if (root == null) {
            result.b = true;
            result.max = Integer.MIN_VALUE;
            result.min = Integer.MAX_VALUE;
            result.count = 0;
            return result;
        }
        ResultType l = sub(root.left);
        ResultType r = sub(root.right);
        if (l.b == true && r.b == true && root.val > l.max && root.val < r.min) {   /*it is a BST */
                result.b = true;  
                result.max = Math.max(root.val, r.max);  
                result.min = Math.min(root.val, l.min);  
                result.count = l.count + r.count + 1;   /*update count */
                return result;
        }
        result.b = false;    /*not a BST,  need to update boolean b */
        result.count = Math.max(l.count, r.count);   /* not a BST updata count */
        return result;
    }
    public int largestBSTSubtree(TreeNode root) {
        ResultType r = sub(root);
        return r.count;
        
    }
    

    }

    Second Edition: Without using MAX_VALUE and MIN_VALUE

    public class Solution {
    public class ResultType {
        boolean b;
        int max;
        int min;
        int count = -1;
    }
    public ResultType sub(TreeNode root) {
        ResultType result = new ResultType();
        if (root == null) {
            result.b = true;
            return result;
        }
        ResultType l = sub(root.left);
        ResultType r = sub(root.right);
        if (l.b == true && r.b == true) {
            if (root.left == null && root.right == null) {
                result.b = true;
                result.max = root.val;
                result.min = root.val;
                result.count = 1;
                return result;
            }
            if (root.left == null && root.right != null && root.val < r.min) {
                result.b = true;
                result.max = r.max;
                result.min = root.val;
                result.count = r.count + 1;
                return result;
            }
            if (root.left != null && root.right == null && root.val > l.max) {
                result.b = true;
                result.max = root.val;
                result.min = l.min;
                result.count = l.count + 1;
                return result;
            }
            if (root.left != null && root.right != null && root.val > l.max && root.val < r.min) {
                result.b = true;
                result.max = r.max;
                result.min = l.min;
                result.count = l.count + r.count + 1;
                return result;
            }
        }
        result.b = false;
        result.count = Math.max(l.count, r.count);
        return result;
    }
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ResultType r = sub(root);
        return r.count;
        
    }
    

    }


Log in to reply
 

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