# Largest BST Subtree

[https://leetcode.com/problems/largest-bst-subtree/description/](https://leetcode.com/problems/largest-bst-subtree/description/)

> 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?

## Thoughts

分治, 检查当前点是否满足BST条件, 即当左右子树都是BST时,node.val比左子树最大值大, 比右子树最小值小. 因此局部需要保存三个值, res\[0]保存当前节点和子树构成bst时的size, 置为-1如果不能构成bst, res\[1]保存能构成bst时整棵子树的最小值, res\[2]保存子树最大值. 外加一个全局变量保存全局当前能构成的最大bst是多大.

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    private int[] helper(TreeNode root) {
        int[] res = new int[3]; // res, min, max
        if (root == null) {
            return res;
        }

        int[] left = helper(root.left);
        int[] right = helper(root.right);

        if (left[0] == -1 || right[0] == -1 || left[0] != 0 && root.val <= left[2] || right[0] != 0 && root.val >= right[1]) {
            res[0] = -1;
            return res;
        }

        res[0] = left[0] + right[0] + 1;
        max = Math.max(max, res[0]);
        res[1] = left[0] == 0 ? root.val : left[1];
        res[2] = right[0] == 0 ? root.val : right[2];

        return res;
    }

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

## Analysis

时间复杂度O(N).
