333. Largest BST Subtree

Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all of its descendants. Here's an example:

10
/ \

5 15 / \ \ 1 8 7

The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public class Result{
        int count;
        Integer max;
        Integer min;
        public Result(int count, Integer max, Integer min){
            this.count = count;
            this.max = max;
            this.min = min;
        }
    }

    private int max = 0;

    public int largestBSTSubtree(TreeNode root) {
        max = 0;
        bstCount(root);
        return max;
    }

    public Result bstCount(TreeNode root){
        if(root == null) return new Result(0, null, null);
        Result left = bstCount(root.left);
        Result right = bstCount(root.right);
        boolean valid = left.count != -1 && right.count != -1 && (left.max == null || root.val > left.max) && (right.min == null || root.val < right.min);
        int max = root.val;
        int min = root.val;
        if(left.max!=null) max = Math.max(max, left.max);
        if(right.max!=null) max = Math.max(max, right.max);
        if(left.min!=null) min = Math.min(min, left.min);
        if(right.min!=null) min = Math.min(min, right.min);
        int count = valid ? left.count + right.count + 1 : -1;
        this.max = Math.max(this.max, count);
        return new Result(count, max, min);
    }





    // //return nodes count if it is bst, else return -1
    // private int bstCount(TreeNode root){
    //     if(root == null) return 0;
    //     int count = 0;
    //     int leftCount = bstCount(root.left);
    //     boolean isValid = (prev == null || prev.val < root.val);
    //     prev = root;
    //     int rightCount = bstCount(root.right);
    //     if(leftCount != -1 && isValid && rightCount != -1){
    //         count = leftCount + 1 + rightCount;
    //     }
    //     else{
    //         count = -1;
    //     }
    //     max = Math.max(max, count);
    //     return count;
    // }
}