98. Validate Binary Search Tree
1. Description
Given a binary tree, determine if it is a valid binary search tree (BST).
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
2. Example
Example 1:
Input: [2,1,3]
Output: true
Example 2:
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.
3. Constraints
- The number of nodes in the tree is in the range [1, $10^4$].
- $-2^{31}$ <= Node.val <= $2^{31} - 1$
4. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// bool isValidBST(TreeNode* root)
bool isValidBST(TreeNode *i_root)
{
long leftBoundary = (long)INT_MIN - 1, rightBoundary = (long)INT_MAX + 1;
return isValidBST(i_root, leftBoundary, rightBoundary);
}
bool isValidBST(TreeNode *i_root, long int leftBoundary, long int rightBoundary)
{
if(i_root)
{
if(i_root->val >= rightBoundary || i_root->val <= leftBoundary)
{
return false;
}
return isValidBST(i_root->left, leftBoundary, i_root->val) && isValidBST(i_root->right, i_root->val, rightBoundary);
}
else
{
return true;
}
}
};
4.1 Traversal
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// if we traverse the tree inorder or postorder, and store values
// we could check whther the array is ascend or descend to judge the tree
class Solution
{
private:
void inorderTraverse(TreeNode *i_root, vector<int> &m_nodes)
{
if(!i_root) return;
inorderTraverse(i_root->left, m_nodes);
m_nodes.push_back(i_root->val);
inorderTraverse(i_root->right, m_nodes);
}
public:
// bool isValidBST(TreeNode* root)
bool isValidBST(TreeNode *i_root)
{
vector<int> nodes;
inorderTraverse(i_root, nodes);
for(int i = 1; i < nodes.size(); i++)
{
if(nodes[i] <= nodes[i - 1])
{
return false;
}
}
return true;
}
};