• 注册
    • 查看作者
    • 领扣: 95. 验证二叉查找树

      95. 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

      Example 1:

      Input:  {-1}
      Output:true
      Explanation:
      For the following binary tree(only one node):
      	      -1
      This is a binary search tree.

      Example 2:

      Input:  {2,1,4,#,#,3,5}
      Output: true
      For the following binary tree:
      	  2
      	 / \
      	1   4
      	   / \
      	  3   5
      This is a binary search tree.
      """
      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):
              # write your code here
              return self.BSTHelper(root)
              
              
          def BSTHelper(self, root, minvalue  = -10000000000, maxvalue = 10000000000):
              if not root:
                  return True
              if root.val > minvalue and root.val < maxvalue:
                  left = self.BSTHelper(root.left,minvalue,root.val)
                  right = self.BSTHelper(root.right,root.val,maxvalue)
                  return left and right
              else:
                  return False

      纽约州·法拉盛
    • 0
    • 0
    • 0
    • 504
    • 请登录之后再进行评论

      登录
    • 做任务