Share my Java code. should be easy to understand


  • 0
    A
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
            int[] rst = helper(root);
            return rst[3];
        }
        //rst[0] == -1 if this subtree is not BST
        //rst[1] is the min value in this tree
        //rst[2] is the max value in this tree
        //rst[3] is the max size BST in this tree
        private int[] helper(TreeNode node){
            if(node == null){
                return new int[]{0, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
            }
            int[] l = helper(node.left);
            int[] r = helper(node.right);
            if(l[0] == -1 || r[0] == -1 || node.val <= l[2] || node.val >= r[1]){
                l[0] = -1;
                l[3] = Math.max(l[3], r[3]);
            }else{
                int min = (l[0] == 0)? node.val: l[1];
                int max = (r[0] == 0)? node.val: r[2];
                l[0] = l[0] + r[0] + 1;
                l[1] = min;
                l[2] = max;
                l[3] = l[0];
            }
            return l;
        }
    }
    

Log in to reply
 

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