liondancer

def lowestCommonAncestor(self, root, p, q):
  # O(n) runtime and constant space
  if root in (None, p, q): return root
  left = lowestCommonAncestor(root.left, p, q)
  right = lowestCommonAncestor(root.right, p, q)
  if left and right:
    return root
  if left:
    return left
  return right

liondancer

def lowestCommonAncestor(root, p, q):
  """
  :type root: TreeNode
  :type p: TreeNode
  :type q: TreeNode
  :rtype: TreeNode
  """
  if max(p.val, q.val) < root.val:
    return lowestCommonAncestor(root.left, p, q)
  elif min(p.val, q.val) > root.val:

liondancer

def levelOrder(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if root:
      queue = [root]
      res = []
      while queue:
        tmp = []

liondancer

def isValid(s):
  """
  :type s: str
  :rtype: bool
  """
  if s:
    if len(s) == 1:
      return False
    stack = []
    d = {'[': ']', '(': ')', '{': '}'}

liondancer

import sys
def isValidBST(root, max=sys.maxint, min=-sys.maxint):
  """
  :type root: TreeNode
  :rtype: bool
  """
  if root is None:
      return True
  return root.val < max and root.val > min and isValidBST(root.left, max=root.val, min=min) and isValidBST(root.right, max=max, min=root.val)

liondancer

def maxDepth(root):
  """
  :type root: TreeNode
  :rtype: int
  """
  if root is None:
      return 0
  return max(maxDepth(root.left), maxDepth(root.right))  + 1

liondancer

def minDepth(root):
  """
  :type root: TreeNode
  :rtype: int
  """
  if root is None:
    return 0
  elif root.left is None:
    return minDepth(root.right) + 1
  elif root.right is None:

liondancer

def spiralOrder(matrix):
  """
  :type matrix: List[List[int]]
  :rtype: List[int]
  """
  if len(matrix) == 0:
      return []
  if len(matrix) == 1:
      return matrix[0]

liondancer

def canFinish(numCourses, prerequisites):
  """
  :type numCourses: int
  :type prerequisites: List[List[int]]
  :rtype: bool
  """
  if prerequisites:
    # create graph
    courses = {}

liondancer

def findOrder(numCourses, prerequisites):
  """
  :type numCourses: int
  :type prerequisites: List[List[int]]
  :rtype: List[int]
  """
  if prerequisites:
    d = {}
    for i in range(numCourses):
      d[i] = set()