easy concise java O(n) solusion


  • 0
    R
    /**
     * the core idea is to use an array which in size 3
     * 0: leftBoundary 1:rightBoundary 2:size
     */
    public class Solution {
        private int max ;
        public int largestBSTSubtree(TreeNode root) {
            if(root != null) max = 1;
            largestBST(root);
            return max;
        }
        
        private int[] largestBST(TreeNode root) {
            if(root == null) return null;
            if(root.left == null && root.right == null) return new int[]{root.val, root.val, 1};
            int[] left = largestBST(root.left);
            int[] right = largestBST(root.right);
            int[] res = new int[]{root.val, root.val, 1};
            if((left == null || root.val > left[1]) && (right == null || root.val < right[0])) {
                if(left != null) {
                    res[0] = left[0];
                    res[2] += left[2];
                }
                if(right != null) {
                    res[1] = right[1];
                    res[2] += right[2];
                }
                max = Math.max(max, res[2]);
                return res;
            }
            res[0] = Integer.MIN_VALUE;
            res[1] = Integer.MAX_VALUE;
            return res;
        }
    }

Log in to reply
 

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