My JAVA SOLUTION - BOTTOM UP APPROACH


  • 0
    A

    // x x x
    // / \ / \ /
    // a b a null null a
    public class Solution {
    public int largestBSTSubtree(TreeNode root) {
    if(root==null) return 0;
    if(root.left==null && root.right==null) return 1;
    Result res = helperBST(root);
    return res.maxSize;
    }

    public Result helperBST(TreeNode root){
        // null case check
        if(root==null) return null;
        
        // leaf node case check
        if(root.left==null && root.right==null)
           return new Result(1, root.val, root.val, true);
    
        //postorder traversal - bottom up approach
        Result left = helperBST(root.left);
        Result right = helperBST(root.right);
        
        //result object that needs to send back to the parent
        Result result = new Result(0,0,0,false);
        int max = 0;
        
        //check for 3 different cases 
        if(root.left!=null && root.right!=null){
            if(root.val>left.maxVal && root.val<right.minVal && left.isBST && right.isBST){
               max = left.maxSize + right.maxSize + 1;
               result.isBST = true;
               result.maxVal = right.maxVal;
               result.minVal = left.minVal;
            }else{
               max = Math.max(left.maxSize, right.maxSize);
               result.isBST = false;
            }
        }else if(root.left==null && root.right!=null ){
            if(root.val<right.minVal && right.isBST){
               max = right.maxSize + 1;
               result.isBST = true;
               result.maxVal = right.maxVal;
               result.minVal = root.val;
            }else{
               max = right.maxSize;
               result.isBST = false;
            }
        }else if(root.left!=null && root.right==null){
            if(root.val>left.maxVal && left.isBST){
               max = left.maxSize+1;
               result.isBST = true;
               result.maxVal = root.val;
               result.minVal = left.minVal;
            }else{
               max = left.maxSize;
               result.isBST = false;
            }
        }
         
        //return maxSize
        result.maxSize = max;
        return result;
    }
    
    public class Result{
        int maxSize;
        int minVal;
        int maxVal;
        boolean isBST;
        
        public Result(int maxSize, int minVal, int maxVal, boolean isBST){
            this.minVal = maxSize;
            this.maxVal = minVal;
            this.maxVal = maxVal;
            this.isBST = isBST;
        }
    }
    

    }

    '''


Log in to reply
 

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