c++ solution


  • 0
    Q
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        map<TreeNode*,int> mp;
    public:
        int largestBSTSubtree(TreeNode* root) {
            if(root == nullptr)
                return 0;
            
            queue<TreeNode*> q;
            q.push(root);
            vector<TreeNode*> v;
            while(!q.empty()){
                TreeNode* t = q.front();
                q.pop();
                if(isbst(t,INT_MIN,INT_MAX))
                    v.push_back(t);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            int m = 1;
            for(auto it:v){
                m = max(m, count_node(it));
            }
            return m;
        }
        
        int count_node(TreeNode* root){
            if(root == nullptr)
                return 0;
            if(mp.find(root) != mp.end())
                return mp[root];
            int res = 1;
            res += count_node(root->left) + count_node(root->right);
            mp[root] = res;
            return res;
                
        }
        
        bool isbst(TreeNode* root, int lower, int higher){
            if(root == nullptr )
                return true;
            if(root->val <= lower || root->val >= higher){
                return false;
            }
            
            if(root->left == nullptr && root->right == nullptr)
                return true;
            bool res1 = true;
            
            if(root->left){
                if(root->left->val > root->val)
                    return false;
                res1 = isbst(root->left,lower,root->val);
            }
            if(root->right){
                if(root->right->val < root->val)
                    return false;
                res1 = res1 && isbst(root->right,root->val,higher);
            }
            return res1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.