c++, 16ms solution


  • 0
    class Solution {
    public:
    vector<int> isBSF(TreeNode* root, int &maxLen){
        vector<int> res(3,0);   // save the length of the tree, the minValue, the maxValue
        if (root==NULL) return res;
        if (root->left==NULL && root->right==NULL) {
            maxLen = max(maxLen,1);
            res[0]=1;res[1]=root->val;res[2]=root->val;
            return res;
        }
        vector<int> l,r;
        if (root->left){
            l = isBSF(root->left,maxLen);
            if (l[1]>l[2] || root->val<=l[2]) {
                res[1]=0;res[2]=-1;  // by setting minVal>maxVal, we flag this tree non-BST
                r = isBSF(root->right,maxLen);
                return res;
            }else{
                res[1] = l[1];
                res[0] += l[0];
            }
        }else{
            res[1] = root->val;
        }
        if (root->right){
            r = isBSF(root->right,maxLen);
            if (r[1]>r[2] || root->val>=r[1]) {
                res[1]=0;res[2]=-1;
                return res;
            }else{
                res[0] +=r[0];
                res[2] = r[2];
            }
        }else{
            res[2] = root->val;
        }
        res[0]++;
        maxLen = max(maxLen,res[0]);
        return res;
    }
    
    int largestBSTSubtree(TreeNode* root) {
        int res=0;
        isBSF(root,res);
        return res;
        
    }
    };

Log in to reply
 

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