A bottom up solution in C++


  • 0
    G
    class Solution {
    public:
    
        void Largest(TreeNode *root, int& Count,bool &IsBST,int &MinVal,int &MaxVal)
        {
            if(root == NULL)
            {
                IsBST = true;
                Count = 0;
                MinVal = INT_MAX;
                MaxVal = INT_MIN;
                return;
            }
            
            int CountL = 0;
            int CountR = 0;
            bool IsBSTL = false,IsBSTR = false;
            int MinLeft = INT_MAX, MaxLeft = INT_MIN;
            int MinRight = INT_MAX, MaxRight = INT_MIN;
            
            Largest(root->left,CountL,IsBSTL,MinLeft,MaxLeft);
            Largest(root->right,CountR,IsBSTR,MinRight,MaxRight);
            
            if(IsBSTR && IsBSTL)
            {
                if(MaxLeft <= root->val && MinRight > root->val)
                {
                    IsBST = true;
                    MinVal = min(MinLeft,root->val);
                    MaxVal = max(MaxRight,root->val);
                    Count = CountL + CountR + 1;
                }
                else
                {
                    IsBST = false;
                    Count = max(CountL,CountR);
                }
            }
            else
            {
                IsBST = false;
                Count = max(CountL,CountR);
            }
        }
    
        int largestBSTSubtree(TreeNode* root) 
        {
            int Count = 0;
            bool IsBST = false;
            int MinVal = INT_MAX, MaxVal = INT_MIN;
            Largest(root,Count,IsBST, MinVal, MaxVal);
            return (Count);
        }
    

Log in to reply
 

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