098._validate_binary_search_tree.md

###98. Validate Binary Search Tree

题目:

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

难度:

Easy

以前做过这道题，valid binary tree，需要check两件事：

   			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!");
}

实际上就是每次往下看，node都确保被夹在一个范围。

翻译了一下伪码，AC

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)