O(n) Recursive Solution


  • 0
    Z
        public int largestBSTSubtree(TreeNode root) {
            return dfs(root)[2];
        }
    
        private int[] dfs(TreeNode root) {
            if (root == null) return new int[]{0,0,0};
            int[] left = dfs(root.left);
            int[] right = dfs(root.right);
            if (left[1] < left[0] || right[1] < right[0] || 
                (left[2] != 0 && root.val < left[1]) ||
                (right[2] != 0 && root.val > right[0])) {
                return new int[]{1, 0, Math.max(left[2], right[2])};
            }
    
            int lower = root.val, upper = root.val;
            if (left[2] != 0) lower = left[0];
            if (right[2] != 0) upper = right[1];
            return new int[]{lower, upper, left[2] + right[2] + 1};
        }
    

Log in to reply
 

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