Short C++ recursive solution


  • 0
        bool isValidBST(TreeNode* r) {
            return isBST(r).size() > 0;
        }
        
        // return node value range {min, max} for valid BST and {} for non BST
        vector<int> isBST(TreeNode* r) {
            if (!r) return {INT_MAX, INT_MIN}; // default range for NULL tree
            vector<int> L = isBST(r->left);
            vector<int> R = isBST(r->right);
            if (!L.size() || !R.size()) return {}; // invalid if either left or right subtree is invalid BST
            if ((!r->left || L[1] < r->val) && (!r->right || R[0] > r->val)) {
                return {min(L[0], r->val), max(R[1], r->val)};
            }
            else return {};
        }
    

Log in to reply
 

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