O(N) java solution


  • 0
    S
    public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        //TODO
        //ans[0] isBST, ans[1] maxVal of subtree, ans[2] minVal, ans[3] maxBSTcount
        int[] ans = helper(root); 
        return ans[3];  
    }
    private int[] helper(TreeNode root) {
        if (root == null) {
            return new int[]{1, 0, 0, 0};
        }
        if (root.left == null && root.right == null) {
            return new int[]{1, root.val, root.val, 1};
        }
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        if (left[0] == 0 || right[0] == 0 
            || root.left != null && left[1] >= root.val 
            || root.right != null && right[2] <= root.val) {
            return new int[]{0, 0, 0, Math.max(left[3], right[3])};
        } 
        //root is now a valid BST
        int[] ans = new int[4];
        ans[0] = 1;
        ans[1] = root.right == null ? root.val : right[1];
        ans[2] = root.left == null ? root.val : left[2];
        ans[3] = left[3] + right[3] + 1;
        return ans;
    }
    

    }


Log in to reply
 

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