9ms short and concise C++ solution


  • 0
    M
    struct BSTInfo{
        bool isBST;
        int minVal;
        int maxVal;
        int size;
        
        BSTInfo (bool a, int b, int c, int d) : isBST(a), minVal(b), maxVal(c), size(d) {}
        
    };
    
    class Solution {
    private:
        int maxsize;
        BSTInfo dfs (TreeNode* root) {
            if (!root->left && !root->right) {
                return BSTInfo(true, root->val, root->val, 1);
            }
            
            BSTInfo left = (root->left) ? dfs(root->left) : BSTInfo(true, root->val, INT_MIN, 0);
            BSTInfo right = (root->right) ? dfs(root->right) : BSTInfo(true, INT_MAX, root->val, 0);
            
            if (left.maxVal < root->val && right.minVal > root->val && left.isBST && right.isBST) {
                maxsize = max(maxsize, left.size + right.size + 1);
                return BSTInfo(true, left.minVal, right.maxVal, left.size + right.size + 1);
            } else {
                return BSTInfo(false, root->val, root->val, 1);
            }
        }
    public:
        int largestBSTSubtree(TreeNode* root) {
            if (!root) {
                return 0;
            }
            maxsize = 1;
            dfs(root);
            return maxsize;
        }
    
    };
    

Log in to reply
 

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