Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

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.

A single node tree is a BST

Example

An example:

  2
 / \
1   4
   / \
  3   5

The above binary tree is serialized as {2,1,4,#,#,3,5} (in level order).

Solution

常犯错误就是忽略的等于号

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of binary tree.
    @return: True if the binary tree is BST, or false
    """  
    def isValidBST(self, root):
        isValid,max,min=self.isValidBSTHelper(root)
        return isValid

    def isValidBSTHelper(self, root):
        # write your code here
        if root is None:
            return True, -sys.maxsize, sys.maxsize
        left = self.isValidBSTHelper(root.left)
        right = self.isValidBSTHelper(root.right)
        if left[0] == False or right[0] == False:
            return False, 0, 0
        if root.left and root.val <= left[1]:
            return False, 0, 0
        if root.right and root.val >= right[2]:
            return False, 0, 0
        return True, max(root.val,right[1]), min(root.val, left[2])