recursion solution
# 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.isValidBSTRecur(root,float('-inf'),float('inf'))
def isValidBSTRecur(self,cur,low,high):
if cur is None:return True
return cur.val>low and cur.val<high \
and self.isValidBSTRecur(cur.left,low,cur.val) \
and self.isValidBSTRecur(cur.right,cur.val,high)
Morris Inorder Traversal
# 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
"""
#Morris Inorder Traversal
prev,cur=None,root
while cur:
if cur.left:
node=cur.left
while node.right and node.right!=cur:
node=node.right
if node.right==cur:
if prev and prev.val>=cur.val:
return False
node.right=None
prev=cur
cur=cur.right
else:
node.right=cur
cur=cur.left
else:
#if left tree is empty, compare prev with current node
if prev and prev.val>=cur.val:
return False
#set prev to cur, cur trace back
prev=cur
cur=cur.right
return True
