3 solutions in C++

``````   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;
}
``````

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

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