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.

The subtree which you find must be a binary search tree(BST).

Example 1:

10
/ \
5  15
/ \   \ 
1   8   7
Input:{10,5,15,1,8,#,7}
Output：3
The Largest BST Subtree in this case is :
   5
  / \
 1   8. 
The return value is the subtree's size, which is 3.

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

My Solutions:

这道题可以沿用#98的做法.

public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) return count(root);
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }

    private boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min >= root.val || max <= root.val) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }

    private int count(TreeNode root) {
        if (root == null) return 0;
        return count(root.left) + count(root.right) + 1;
    }
}

为了满足O(n)的要求，可以再优化一下。用一个全局变量count记录最大值。修改helper方程，让他返回一个int[],用来记录几个状态

index[0]：代表此子树是否是bst，1代表是，0代表不是

index[1]：代表此子树的最大值

index[2]：代表此子树的最小值

int count;
public int largestBSTSubtree(TreeNode root) {
    helper(root);
    return count;
}

// 用一个int[]记录几个状态
private int[] helper(TreeNode root) {
    if (root == null) return new int[]{0, 0, 0};
    int[] left = helper(root.left), right = helper(root.right);
    
    // 如果有一个子树不是bst，则不需要进行下去，因为已经更新过count
    if (left[0] == -1 || right[0] == -1) return new int[]{-1, 0, 0};
    
    // 如果左右子树都能接到现在的root上，更新全局变量count
    if ((root.left == null || root.val > left[1]) 
        && (root.right == null || root.val < right[2])) {
        count = Math.max(count, 1 + left[0] + right[0]);
        // 更新最大值和最小值
        int min = root.val, max = root.val;
        if (root.left != null) min = Math.min(min, left[2]);
        if (root.right != null) max = Math.max(max, right[1]);
        return new int[]{1 + left[0] + right[0], max, min};
    } else {
        return new int[]{-1, 0, 0};
    }
}