Trees — Complete Guide: All Patterns & Problem Index

def inorder(root):
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def inorder_iter(root):
    stack, result = [], []
    curr = root
    while curr or stack:
        while curr: stack.append(curr); curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

from collections import deque
def level_order(root):
    if not root: return []
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

def has_path_sum(root, target):
    if not root: return False
    if not root.left and not root.right: return root.val == target
    return has_path_sum(root.left, target-root.val) or            has_path_sum(root.right, target-root.val)

def lca(root, p, q):
    if not root or root == p or root == q: return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    return root if left and right else left or right

def diameter(root):
    self.ans = 0
    def depth(node):
        if not node: return 0
        L, R = depth(node.left), depth(node.right)
        self.ans = max(self.ans, L+R)
        return max(L, R)+1
    depth(root)
    return self.ans