2 ms Java Solution


  • 0
    D
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
            if( root == null ) return 0;
            int [] ret = helper( root );
            return ret[3];
        }
        
        private int[] helper( TreeNode node ) {
            int[] l = new int[]{ 1, node.val, node.val, 0 }; //isBst, min, max, numNodesBST
            int[] r = new int[]{ 1, node.val, node.val, 0 };
            
            if( node.left != null ) l = helper ( node.left );
            if( node.right != null ) r = helper ( node.right );
            
            boolean isBst = l[0] == 1 && r[0] == 1 && node.val >= l[2] && node.val <= r[1];
                
            int numBstNodes = isBst ? 1 + l[3] + r[3] : Math.max( l[3], r[3] );
            
            return new int[]{ isBst ? 1 : 0, l[1], r[2], numBstNodes };
        }
    }

Log in to reply
 

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