Validate Binary Search Tree Problem: Given the root
of a binary tree, determine if it is a valid binary search tree (BST).
Input: root = [2,1,3] Output: true
Table of Contents
Validate Binary Search Tree Problem Solution
Problem Solution In Python
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def inorder(root):
if root.left:
inorder(root.left)
res.append(root.val)
if root.right:
inorder(root.right)
res=[]
if root:
inorder(root)
for i in range(1,len(res)):
if res[i-1]>=res[i]:
return False
return True
Problem Solution In Java
List<Integer> sol = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
dfs(root);
for(int i=1; i<sol.size(); i++)
if(sol.get(i-1)>=sol.get(i))
return false;
return true;
}
public void dfs(TreeNode root) {
if(root==null) return;
dfs(root.left);
sol.add(root.val);
dfs(root.right);
}
Problem Solution In C++
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root,NULL,NULL);
}
bool helper(TreeNode* root, TreeNode* min, TreeNode* max)
{
if(root==NULL)
return true;
else if(min!=NULL && root->val<=min->val || max!=NULL && root->val>=max->val)
return false;
else if( helper(root->left, min, root) && helper(root->right, root, max))
return true;
return false;
}
};
Problem Solution In C
bool check(struct TreeNode* root, int* min, int* max) {
if (root == NULL) {
return true;
}
if ((min != NULL && root->val <= *min) || (max != NULL && root->val >= *max)) {
return false;
}
return check(root->left, min, &root->val) && check(root->right, &root->val, max);
}
bool isValidBST(struct TreeNode* root){
return check(root, NULL, NULL);
}