LeetCode Solutions
98. Validate Binary Search Tree
Time: $O(n)$ Space: $O(h)$
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, nullptr, nullptr);
}
private:
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (root == nullptr)
return true;
if (minNode && root->val <= minNode->val)
return false;
if (maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) &&
isValidBST(root->right, root, maxNode);
}
};
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode root, TreeNode minNode, TreeNode maxNode) {
if (root == null)
return true;
if (minNode != null && root.val <= minNode.val)
return false;
if (maxNode != null && root.val >= maxNode.val)
return false;
return isValidBST(root.left, minNode, root) &&
isValidBST(root.right, root, maxNode);
}
}
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidBST(root: Optional[TreeNode],
minNode: Optional[TreeNode], maxNode: Optional[TreeNode]) -> bool:
if not root:
return True
if minNode and root.val <= minNode.val:
return False
if maxNode and root.val >= maxNode.val:
return False
return isValidBST(root.left, minNode, root) and \
isValidBST(root.right, root, maxNode)
return isValidBST(root, None, None)