98-Validate-Binary-Search-Tree https://leetcode.com/problems/validate-binary-search-tree/
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.prev = None
return self.isMonotonicIncreasing(root)
def isMonotonicIncreasing(self, node):
if node == None:
return True
if not self.isMonotonicIncreasing(node.left):
return False
if self.prev != None and self.prev.val >= node.val:
return False
self.prev = node
if not self.isMonotonicIncreasing(node.right):
return False
return True
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.recursive(-float('inf'), root, float('inf'))
def recursive(self, lowBound, node, highBound):
if node == None:
return True
return node.val < highBound and node.val > lowBound and\
self.recursive(lowBound, node.left, node.val) and self.recursive(node.val, node.right, highBound)
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
2
/ \
1 3
Binary tree [2,1,3]
, return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3]
, return false.