Easy-to-understand Java Solution


  • 0
    public class Solution {
        
        class Res {
            boolean isBST;
            int count;
            int firstVal;
            int lastVal;
            Res (boolean isBST, int count, int firstVal, int lastVal) {
                this.isBST = isBST;
                this.count = count;
                this.firstVal = firstVal;
                this.lastVal = lastVal;
            }
        }
        
        int maxCount = 0;
        
        public Res helper(TreeNode root) {
            if(root==null)
                return new Res(true, 0, 0, 0);
            Res lRes = helper(root.left);
            Res rRes = helper(root.right);
            if(lRes.isBST && rRes.isBST) {
                int preVal = lRes.count==0 ? root.val-1 : lRes.lastVal;
                int nextVal = rRes.count==0 ? root.val+1 : rRes.firstVal;
                if(preVal<root.val && nextVal>=root.val) {
                    int count = lRes.count + rRes.count + 1;
                    maxCount = count > maxCount ? count : maxCount; // side-effect
                    return new Res(true, count, lRes.count==0?root.val:lRes.firstVal, rRes.count==0?root.val:rRes.lastVal);
                }
                return new Res(false,0,0,0);
            }
            return new Res(false,0,0,0);
        }
        
        public int largestBSTSubtree(TreeNode root) {
            helper(root);
            return maxCount;
        }
    }

Log in to reply
 

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