98. Validate Binary Search Tree - cocoder39/coco39_LC GitHub Wiki
98. Validate Binary Search Tree
in order traversal
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
stack = []
pre, cur = None, root
while stack or cur:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre and pre.val >= cur.val:
return False
pre = cur
cur = cur.right
return True
Main idea is checking if the inorder traversal sequence is in ascending order. [link to inorder traversal]
A corner case is that the first element is INT_MIN, which is equal to initial pre.
O(n) time and O(h) space where n is number of nodes in tree and h is height
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* cur = root;
bool first = true;
int pre = INT_MIN;
while (cur || ! s.empty()) {
if (cur) {
s.push(cur);
cur = cur->left;
} else {
TreeNode* node = s.top();
s.pop();
if (! first && node->val <= pre) {
return false;
}
first = false;
pre = node->val;
cur = node->right;
}
}
return true;
}
inorder recursion
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* pre = nullptr;
return helper(root, &pre);
}
private:
bool helper(TreeNode* root, TreeNode** pre) {
if (!root) {
return true;
}
if (!helper(root->left, pre)) {
return false;
}
if (*pre && (*pre)->val >= root->val) {
return false;
}
*pre = root;
return helper(root->right, pre);
}
};
recursive solution: use long to handle corner case where the tree contains node with value INT_MAX/INT_MIN
visit each node once, time is O(n), space is O(h)
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
private:
bool helper(TreeNode* root, long low, long high) {
if (! root) return true;
if (root->val <= low || root->val >= high) return false;
return helper(root->left, low, root->val) &&
helper(root->right, root->val, high);
}
};
if not allowed using LONG
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root, nullptr, nullptr);
}
private:
bool helper(TreeNode* root, TreeNode* low, TreeNode* high) {
if (! root) return true;
if ((low && root->val <= low->val) || (high && root->val >= high->val)) return false;
return helper(root->left, low, root) &&
helper(root->right, root, high);
}
};