3 solutions in C++


  • 2
    X

    For your reference.

       bool isValidBST1(TreeNode *root) {
            long min_val, max_val;
     
            return isValidBSTHelper(root, min_val, max_val);
        }
     
        // decide if tree is BST; return min and max of it
        bool isValidBSTHelper(TreeNode *root, long &min_val, long &max_val) {
            if (!root) {
                min_val = LONG_MAX;
                max_val = LONG_MIN;
                return true;
            }
     
            long l_min, l_max, r_min, r_max;
            bool is_left_valid = isValidBSTHelper(root->left, l_min, l_max);
            bool is_right_valid = isValidBSTHelper(root->right, r_min, r_max);
     
            min_val = min(l_min, r_min);
            min_val = min(min_val, (long)root->val);
            max_val = max(l_max, r_max);
            max_val = max(max_val, (long)root->val);
     
            return (is_left_valid && is_right_valid && l_max < root->val && r_min > root->val);
        }
     
    
        bool isValidBST2(TreeNode *root) {
            return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
        }
     
        // decide if tree is a BST within range (lower, upper), exclusive
        bool isValidBSTHelper(TreeNode *root, long lower, long upper) {
            if (!root)  return true;
     
            long val = (long)root->val;
            return (val > lower && val < upper && isValidBSTHelper(root->left, lower, val) && isValidBSTHelper(root->right, val, upper));
        }
    
    
    
       bool isValidBST3(TreeNode *root) {
            long last = LONG_MIN;
            return inorderTraverse(root, last);
        }
    
        // if tree @root is a BST, i.e., in-order traversal is increasing
        bool inorderTraverse(TreeNode *root, long &last) {
            if (!root)  return true;
    
            if (!inorderTraverse(root->left, last))   return false;
            
            if (last >= root->val)
                return false;
            last = root->val;
            
            if (!inorderTraverse(root->right, last))  return false;
            return true;
        }
    

  • 0
    A

    mark, i just think of the first solution, 2 and 3 is really smart!!


Log in to reply
 

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