Question: https://oj.leetcode.com/problems/validate-binary-search-tree/
Question Name: Validate Binary Search Tree
This is an extension of an older question Binary Tree Inorder Traversal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of integers def inorderTraversal(self, root): # Handle with the special cast (empty input) if root == None: return [] stack = [root] current = root.left result = [] while len(stack) != 0 or current != None: # Find the leftmost node among all the un-accessed ones. while current != None: stack.append(current) current = current.left # Fetch the value in currently leftmost node current = stack.pop() result.append(current.val) # Try the right son of current node current = current.right return result # @param root, a tree node # @return a boolean def isValidBST(self, root): inOrder = self.inorderTraversal(root) # If root is a binary search tree, the result of in order # travle will be strickly increasing. for index in xrange(len(inOrder)-1): if inOrder[index] >= inOrder[index+1]: return False return True |
2 years later…time machine:)
The machine is working on only one direction 🙂