My recursive short solution


  • 0
    H
    public class Solution {
        int max = Integer.MIN_VALUE;
        public int largestBSTSubtree(TreeNode root) {
            if(root == null) return 0;
            Help(root);
            return max;
        }
        
    //returned int[]{minum val of sub tree, maximum val of sub tree, is BST, size of sub tree}
        private int[] Help(TreeNode root){
            if(root == null) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 1, 0};
            int[] left = Help(root.left);
            int[] right = Help(root.right);
            if(left[2] == 1 && right[2] == 1 && left[1] < root.val && right[0] > root.val){
                max = Math.max(left[3] + right[3] + 1, max);
                return new int[]{Math.min(root.val, left[0]), Math.max(root.val, right[1]), 1, left[3] + right[3] + 1};
            }
            else{
                return new int[]{0,0,0};
            }
        }
    }
    

Log in to reply
 

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