[Leetcode 333] 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. e.g.

  5  
 / \
1   8

The return value is the subtree's size, which is 3.

Hint:
You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

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

Diffculty
Medium

Similar Problems
[LeetCode 98] Validate Binary Search Tree Medium

Analysis

首先需要及其注意 BST 的定义：也即当前节点必须大于左子树中的所有节点，并且小于右子树中的所有节点。也即 root->val < left->max && root->val > right->min。

如下：根节点是 10，但是左子树最大的节点是 18，显然不符合 BST 的定义。

   10
   / \
  5  15
 / \   \ 
1   8  
     \
      18

判断每个子节点的最大 BST。如果是 Top Down 方式的话，时间复杂度是 O(n!)，对于很大的树极为耗时， 如果采用 Bottom Up 的方式，那么时间复杂度降为 O(N)，问题的关键在于采用 Bottom Up 我们需要从子树获得哪些信息?

从 BST 的性质来说，我们显然需要知道左子树的最大值 leftMax 和右子树的最小值 rightMin。当然，还需要分别知道左子树和右子树的 BST 大小。总结下来就是下面几个：

• (1) 子树是不是BST
• (2) MAX VALUE in this sub tree
• (3) min value in this sub tree

如果左右子树都是 BST，显然，当前节点就可以标记为也是 BST 了，并且 BST 的 size 可以更新为 left->size + right->size + 1。 如果左右子树有任何一个不是 BST，那么就可以当前节点标记成 false, 同时更新 size 为 max(leftSize, rightSize)。

这道题的核心思想是：post order, 左-右-中。 首先递归得到左右子树的结果，然后如果当前节点的值满足在 (left->max, right->min) 区间，且左右子树都是 BST，则可以标记以当前节点为根的子树也是 BST。

• (1) 当前节点的左右子树都是 BST, 如果 root 也满足要求，则把 root 更新。
• (2) 当前节点的左右子树有一个不是 BST, 那么就把 root 设成 false, 然后更新 size 为 left 和 right 最小的。
• (3) 当前节点为空。

class Solution {
public:
    class Result  {
    public:
        bool isBST;
        int size, min, max;
        Result (bool a, int b, int c, int d): isBST(a), size(b), min(c), max(d) {}
    };

    int largestBSTSubtree(TreeNode* root) { // postorder traverse, maintain a true/false, size, min and max
        Result *res = helper(root);
        return res->size;
    }

    Result* helper(TreeNode *root) {
        if (root == nullptr) {
            return new Result(true, 0, INT_MAX, INT_MIN);
        }

        Result *left = helper(root->left);
        Result *right = helper(root->right);

        if (!left->isBST || !right->isBST || root->val > right->min || root->val < left->max) {
            return new Result (false, max(left->size, right->size), INT_MAX, INT_MIN);
        }

        Result *res = new Result(true, 0 , 0, 0);
        res->isBST = true;
        res->size = left->size + right->size + 1;
        res->min = root->left == nullptr ? root->val : left->min;
        res->max = root->right == nullptr ? root->val : right->max;
        return res;

    }
};