# 098 validate binary search tree

### 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

Easy

            10
/  \
7   20
/ \
5  40

• node.left.val < node.val
• right subtree of left child, value < node.val
• node.right.val > node.val
• left subtree of the right child, value > node.val

wikipedia上有伪码：

truct TreeNode {
int key;
int value;
struct TreeNode *left;
struct TreeNode *right;
};

bool isBST(struct TreeNode *node, int minKey, int maxKey) {
if(node == NULL) return true;
if(node->key < minKey || node->key > maxKey) return false;

return isBST(node->left, minKey, node->key) && isBST(node->right, node->key, maxKey);
}

if(isBST(root, INT_MIN, INT_MAX)) {
puts("This is a BST.");
} else {
puts("This is NOT a BST!");
}


class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isBST(root, float('-inf'),float('inf'))

def isBST(self, root, minKey, maxKey):
if root == None: return True
if root.val <= minKey or root.val >= maxKey : return False
return self.isBST(root.left,minKey,root.val) and self.isBST(root.right, root.val, maxKey)


apachecn/AiLearning