Java 3-element array Top-Down O(n)


  • 0
        public int largestBSTSubtree(TreeNode root) {
            int[] size = {0};
            helper(root, size);
            return size[0];
        }
        
        private int[] helper(TreeNode root, int[] size) { // array
            int[] res = new int[3]; // nums, min, max
            res[0] = 0;
            res[1] = Integer.MAX_VALUE; // min
            res[2] = Integer.MIN_VALUE; // max
            if (root == null) return res;
            
            int[] left = helper(root.left, size);
            int[] right = helper(root.right, size);
            if (left[0] == -1 || right[0] == -1) {
                res[0] = -1;
            } else {
                if (root.val > left[2] && root.val < right[1]) {
                    res[0] = 1 + left[0] + right[0];
                    if (res[0] > size[0]) size[0] = res[0];
                    res[1] = Math.min(root.val, left[1]);
                    res[2] = Math.max(root.val, right[2]);
                } else {
                    res[0] = -1;
                }            
            }
            return res;
        }
    

Log in to reply
 

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