Simple 17ms recursive C++ solution


  • 1
    Y

    Use two values to check if the node is valid

    class Solution {
    public:
        bool dfs(TreeNode *root, long kmin, long kmax)
        {
            if(!root) return true;
            
            long val = (long)root->val;
            
            if(val >= kmax) return false;
            if(val <= kmin) return false;
            
            if(!dfs(root->left, kmin, min(kmax, val))) return false;
            
            if(!dfs(root->right, max(val, kmin), kmax)) return false;
            
            return true;
        }
        
        bool isValidBST(TreeNode *root) 
        {
            if(!root) return true;
            
            if(!dfs(root->left, LONG_MIN, root->val)) return false;
            
            return dfs(root->right, root->val, LONG_MAX); 
        }
    };

Log in to reply
 

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