二叉树

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def is_same_tree(p, q):
      if p is None:
          return not q
      if q is None:
          return not p
      return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

def is_symmetric(root):
    if not root:
        return True
    return symmetric(root.left, root.right)


def symmetric(l1, l2):
    if l1 is None:
        return not l2
    if l2 is None:
        return not l1
    return l1.val == l2.val and symmetric(l1.left, l2.right) and symmetric(l1.right, l2.left)

def add(node, level, res):
    if node is None:
        return
    if len(res) < level:
        res.append([])
    res[level - 1].append(node.val)
    add(node.left, level + 1, res)
    add(node.right, level + 1, res)

def level_order(root):
    res = []
    add(root, 1, res)
    return res

def max_depth(root):
    return 1 + max(map(max_depth, (root.left, root.right))) if root else 0

def min_depth(root):
    if root is None:
        return 0
    if root.left is None:
        return 1 + min_depth(root.right)
    if root.right is None:
        return 1 + min_depth(root.left)
    return 1 + min(map(min_depth, (root.left, root.right)))

# 更简洁的写法
def min_depth(root):
    if root is None:
        return 0
    depth_under_root = map(min_depth, (root.left, root.right))
    return 1 + (min(depth_under_root) or max(depth_under_root))

def sorted_array_to_balanced_tree(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_balanced_tree(nums[:mid])
    root.right = sorted_array_to_balanced_tree(nums[mid + 1:])

def hight(node):
    if node is None:
        return 0
    return 1 + max(map(hight, (node.left, node.right)))

def is_balanced(root):
    if root is None:
        return True
    return abs(hight(root.left) - hight(root.right)) <= 1 and is_balanced(root.left) and is_balanced(root.right)

def has_path_sum(root, sums):
    if root is None:
        return False
    if root.left or root.right:
        return has_path_sum(root.left, sums - root.val) or has_path_sum(root.right, sums - root.val)
    return sums == root.val