# My AC Python codes

• At first, I validate the tree directly based on the definition of a BST (each node is bigger than its left sub-tree and smaller than its right sub-tree). So I just traverse the tree and check every node.

``````# 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
"""
def check(r, val, left):
if r == None:
return True
if left and r.val >= val:
return False
elif not left and r.val <= val:
return False
return check(r.left, val, left) and check(r.right, val, left)

def traverse(r):
if r == None:   return True
if not (check(r.left, r.val, True) and check(r.right, r.val, False)): return False
return traverse(r.left) and traverse(r.right)

return traverse(root)
``````

Actually, we can also validate the condition that each node is larger than previously visited node. So we can apply inorder traversal while recording a 'pre' node. Following is a recursive implementation.

``````class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.pre = ListNode(-2**32)
def inorder(r):
if r == None:
return True
a = inorder(r.left)
if r.val <= self.pre.val:
return False
self.pre = r
b = inorder(r.right)
return a and b

return inorder(root)
``````

And this is a iterative implementation.

``````class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
pre = ListNode(-2**32)
node, stack = root, []
while node!=None or stack:
while node != None:
stack.append(node)
node = node.left
node = stack.pop()
if node.val <= pre.val:
return False
pre = node
node = node.right

return True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.