333. Largest BST Subtree

alg 1: take advantage of 98. Validate Binary Search Tree. Call isValidBST at each node. T(n) = 2T(n/2) + O(n) = O(n * log n)

alg2: to check if a new node is a root of a bst, we need verify

if both its left and right subtree are bst (thus we need record if a subtree a BST)
if its value is greater than upper bound of left subtree and lower than lower bound of right subtree (thus we need record the bounds of a bst)
if it is a bst, accumulate the # of bst (thus need record the number of bst within a subtree)

Use Result to preserve the properties of a bst whose root is root. A node is the root of a bst iff

left.isBST && right.isBST
root->val > left.maxi && root->val < right.mini

To make the leave node meets the requirement that root->val > left.maxi && root->val < right.mini, set res = Result(0, INT_MAX, INT_MIN, true) when root == nullptr

A key point is updating the min, max val of current bst. Take res.mini for example, res.mini = left.mini if left sub tree is not empty; otherwise res.mini = root->val.

T = O(N) and S = O(height)

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        Result res = helper(root);
        return res.sz;
    }
private:
class Result {
        public:
            int sz; 
            int low; //min val of the bst whose root is current node
            int high; 
            bool isBST;
            Result() = default;
            Result(int sz, int low, int high, bool isBST) {
                this->sz = sz; 
                this->low = low; 
                this->high = high; 
                this->isBST = isBST; 
            }
    };
    Result helper(TreeNode* root) {
        Result res;
        if (! root) {
            res = Result(0, INT_MAX, INT_MIN, true);
            return res;
        }
        
        Result left = helper(root->left);
        Result right = helper(root->right);
        
        if (left.isBST && right.isBST && root->val > left.high && root->val < right.low) {
            int low = root->left ? left.low : root->val;
            int high = root->right ? right.high : root->val;
            res = Result(left.sz + right.sz + 1, low, high, true);
        }
        else {
            res = Result(max(left.sz, right.sz), INT_MAX, INT_MIN, false);
        }   
        return res;
    }
};

solution 2: basic idea is same as solution 1, different coding style

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        int res, high, low;
        isBST(res, high, low, root);
        return res;
    }
private:
    bool isBST(int& res, int& low, int& high, TreeNode* root) {
        if (! root) {
            res = 0;
            low = INT_MAX;
            high = INT_MIN;
            return true;
        }
        
        int left_res, left_low, left_high;
        bool left = isBST(left_res, left_low, left_high, root->left);
        
        int right_res, right_low, right_high;
        bool right = isBST(right_res, right_low, right_high, root->right);
        
        if (left && right && root->val > left_high && root->val < right_low) {
            low = min(left_low, root->val);
            high = max(right_high, root->val);
            res = left_res + right_res + 1;
            return true;
        }
        else {
            res = max(left_res, right_res);
            return false;
        }
    }
};

333. Largest BST Subtree - cocoder39/coco39_LC GitHub Wiki