Largest BST Subtree(Leetcode 333)

这道题有两种解法。一种top down O(nlong(n)), 另外一种bottom up O(n)。

For bottom up approach, (重点是) 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，两种区别在于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;
    }
};