leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

validate-binary-search-tree.py (741B)

      1 # IDEAS:
      2 
      3 # 1) Perform in-order traversal then verify ordering of the result
      4 # TIME: O(n) SPACE: O(n)
      5 
      6 
      7 class Solution:
      8     def isValidBST(self, root: Optional[TreeNode]) -> bool:
      9 
     10         if root is None:
     11             return True
     12 
     13         in_order = dfs_in_order(root)
     14 
     15         for i in range(0, len(in_order) - 1):
     16             if in_order[i] >= in_order[i + 1]:
     17                 return False
     18         return True
     19 
     20 
     21 # Return a list of nodes
     22 def dfs_in_order(root):
     23 
     24     if root is None:
     25         return None
     26 
     27     left = dfs_in_order(root.left)
     28     if left is not None:
     29         left.append(root.val)
     30     else:
     31         left = [root.val]
     32 
     33     right = dfs_in_order(root.right)
     34 
     35     if right is not None:
     36         left.extend(right)
     37 
     38     return left