這道題有兩種解法。一種top down O(nlong(n)), 另外一種bottom up O(n)。

For bottom up approach, (重點(diǎn)是) in order for tree to be valid, root value needs to be greater than the max of left subtree, and the min of right subtree.

class Solution {
    
    struct ResultSet {
        bool isTree;
        int min_value, max_value;
        int max_cnt;
        ResultSet(bool b, int mi, int mx) : isTree(b), min_value(mi), max_value(mx), max_cnt(0) {}
    };
    
public:
    
    ResultSet FindTree(TreeNode * root){
        if(!root){
            return ResultSet(true, INT_MAX, INT_MIN);
        }
        ResultSet rt(true, 0, 0);
        
        
        ResultSet left = FindTree(root->left);
        ResultSet right = FindTree(root->right);
        
        rt.min_value = min(root->val, min(left.min_value, right.min_value));
        rt.max_value = max(root->val, max(left.max_value, right.max_value));
        
        if(left.isTree && right.isTree) {
            if(root->val > left.max_value && root->val < right.min_value) {
                rt.max_cnt = max(rt.max_cnt, left.max_cnt + right.max_cnt + 1);
                return rt;
            }
        }
        rt.isTree = false;
        rt.max_cnt = max(left.max_cnt, right.max_cnt);
        return rt;
    }
    
    int largestBSTSubtree(TreeNode* root) {
        if(!root) {
            return 0;
        }
        
        ResultSet rs = FindTree(root);
        return rs.max_cnt;
    }
};

其中，最大值直接取左中右的max，最小值直接取左中右的min，并不需要想太多。

        ret.max_value = max(root->val, max(left.max_value, right.max_value));
        ret.min_value = min(root->val, min(left.min_value, right.min_value));

Top down approach 有兩種，一種是top down+ top down, 另外一種是top down + bottom up，兩種區(qū)別在于find_tree utility function.

class Solution {
public:
    
    void FindTree_util(TreeNode *root, TreeNode *large, TreeNode *small, int &cur) {
        if(!root) return;
        if(large && large->val <= root->val) {
            cur = -1;
            return;
        }                                                                          
        else if(small && small->val >= root->val) {
            cur = -1;
            return;
        }
        
        cur = cur + 1;
        FindTree_util(root->left, root, small, cur);
        FindTree_util(root->right, large, root, cur);
    }
    
    void FindTree(TreeNode* root, int &max_ret) {
        if(!root) return;
        int cur = 0;
        FindTree_util(root, NULL, NULL, cur);
        if(cur != -1){
            max_ret = max(max_ret, cur);
        }
        FindTree(root->left, max_ret);
        FindTree(root->right, max_ret);
    }
    
    int largestBSTSubtree(TreeNode* root) {
        if(!root) {
            return 0;
        }
        
        int max_ret = 0;
        FindTree(root, max_ret);
        return max_ret;
    }
};

class Solution {
public:
    
    int FindTree_util(TreeNode *root, TreeNode *large, TreeNode *small) {
        if(!root) return 0;
        if(large && large->val <= root->val) {
            return -1;
        }                                                                          
        else if(small && small->val >= root->val) {
            return -1;
        }
        
        int left_value = FindTree_util(root->left, root, small);
        if(left_value == -1) {
            return -1;
        }
        
        int right_value = FindTree_util(root->right, large, root);
        if(right_value == -1) {
            return -1;
        }
        
        return left_value + right_value + 1;
    }
    
    void FindTree(TreeNode* root, int &max_ret) {
        if(!root) return;
        int ret = FindTree_util(root, NULL, NULL);
        if(ret > max_ret) {
            max_ret = ret;
        }
        FindTree(root->left, max_ret);
        FindTree(root->right, max_ret);
    }
    
    int largestBSTSubtree(TreeNode* root) {
        if(!root) return 0;
        int max_ret = 0;
        FindTree(root, max_ret);
        return max_ret;
    }
};