C++ code (not a new algorithm but very descriptive and zero bugs)


  • 0
    G
    class Solution {
        bool is_leaf(TreeNode* node) {
            return ((node != NULL) && (node->left == NULL) && (node->right == NULL));
        }
        
        bool _isValidBST(TreeNode* root, int* min, int* max) {
            if (!root) return true; // to handle NULL root case
    
            *min = *max = root->val;
            if (is_leaf(root)) return true; // a leaf node is always a valid BST in itself
    
            // at this point we know it's not a leaf node
            if (root->left != NULL) {
                int l_min, l_max;
                bool is_left_bst = _isValidBST(root->left, &l_min, &l_max);;
                if (is_left_bst == false || l_max >= root->val) return false;
                *min = l_min;   // adjust the 'min' since left subtree exists
            }
          
            if (root->right != NULL) {
                int r_min, r_max;
                bool is_right_bst = _isValidBST(root->right, &r_min, &r_max);
                if (is_right_bst == false || r_min <= root->val) return false;
                *max = r_max;   // adjust the 'max' since right subtree exists
            }
            
            return true;
        }
        
    public:
        bool isValidBST(TreeNode* root) {
            // Every node should maintain the invariant that it's value is
            // > the max of the left subtree (if exists) and < the min of
            // the right subtree (if exists), then it will be a valid BST
            int min, max;
            return _isValidBST(root, &min, &max);
        }
    };
    

Log in to reply
 

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