Easy Java Solution


  • 0
    Y

    Bottom-up recursive approach. When subtree is a valid BST, we return an array with three values: {min value of subtree, max value of subtree, size of subtree}. When subtree is not a valid BST, return null. That should be enough for us to determine whether tree at current root is a BST or not (if one subtree is invalid, its parent tree is also invalid, otherwise check max(left subtree) < root && min(right_subtree) > root). We can either update result or return null to indicate an invalid BST.

    public class Solution {
        private int result = 0;
        
        public int largestBSTSubtree(TreeNode root) {
            largest(root);
            return result;
        }
        
        private int[] largest(TreeNode root) {
            if (root == null) {
                // if root is null, set min to MAX_VALUE and max to MIN_VALUE
                return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
            }
            int[] left = largest(root.left);
            int[] right = largest(root.right);
            if (left == null || right == null) {
                return null;
            }
            if (left[1] < root.val && right[0] > root.val) {
                result = Math.max(result, left[2]+1+right[2]);
                // if left/right child is null, use current value as boundary
                int leftMin = root.left == null? root.val : left[0];
                int rightMax = root.right == null ? root.val : right[1];
                // return {min, max, size}
                return new int[]{leftMin, rightMax, left[2]+1+right[2]};
            }
            return null;
            
        }
    }
    

Log in to reply
 

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