Trees and Traversals

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

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

def preorder(root, out):     # root, left, right
    if not root:
        return
    out.append(root.val)
    preorder(root.left, out)
    preorder(root.right, out)

def inorder(root, out):      # left, root, right -> sorted for a BST
    if not root:
        return
    inorder(root.left, out)
    out.append(root.val)
    inorder(root.right, out)

def postorder(root, out):    # left, right, root -> children before parent
    if not root:
        return
    postorder(root.left, out)
    postorder(root.right, out)
    out.append(root.val)

def preorder_iter(root):
    if not root:
        return []
    out, st = [], [root]
    while st:
        node = st.pop()
        out.append(node.val)
        if node.right:
            st.append(node.right)     # right first, so left pops first
        if node.left:
            st.append(node.left)
    return out

def inorder_iter(root):
    out, st, cur = [], [], root
    while cur or st:
        while cur:
            st.append(cur)
            cur = cur.left            # dive left as far as possible
        cur = st.pop()
        out.append(cur.val)
        cur = cur.right
    return out

def postorder_iter(root):
    """Reverse of a modified preorder: root, right, left, then reverse."""
    if not root:
        return []
    out, st = [], [root]
    while st:
        node = st.pop()
        out.append(node.val)
        if node.left:
            st.append(node.left)
        if node.right:
            st.append(node.right)
    return out[::-1]

def morris_inorder(root):
    """O(1) space by threading temporary links back to the successor."""
    out, cur = [], root
    while cur:
        if not cur.left:
            out.append(cur.val)
            cur = cur.right
        else:
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if not pre.right:
                pre.right = cur       # thread
                cur = cur.left
            else:
                pre.right = None      # unthread, restore the tree
                out.append(cur.val)
                cur = cur.right
    return out

from collections import deque

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):       # freeze the size, one level per round
            n = q.popleft()
            level.append(n.val)
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        out.append(level)
    return out

def zigzag(root):
    levels = level_order(root)
    return [lv if i % 2 == 0 else lv[::-1] for i, lv in enumerate(levels)]

def right_side_view(root):
    return [lv[-1] for lv in level_order(root)]

def min_depth(root):
    """BFS returns as soon as the first leaf is found."""
    if not root:
        return 0
    q, depth = deque([root]), 1
    while q:
        for _ in range(len(q)):
            n = q.popleft()
            if not n.left and not n.right:
                return depth
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        depth += 1

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

def is_balanced(root):
    """Return height, or -1 to signal unbalanced. O(n) single pass."""
    def h(node):
        if not node:
            return 0
        lh = h(node.left)
        if lh == -1:
            return -1
        rh = h(node.right)
        if rh == -1 or abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)
    return h(root) != -1

def diameter(root):
    """Longest path in edges between any two nodes."""
    best = 0
    def depth(node):
        nonlocal best
        if not node:
            return 0
        l, r = depth(node.left), depth(node.right)
        best = max(best, l + r)       # path THROUGH this node
        return 1 + max(l, r)          # but the parent only gets one side
    depth(root)
    return best

def max_path_sum(root):
    """Values may be negative, so clamp a negative branch to 0."""
    best = float("-inf")
    def gain(node):
        nonlocal best
        if not node:
            return 0
        l = max(gain(node.left), 0)
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best

def count_univalue_subtrees(root):
    count = 0
    def walk(node):
        nonlocal count
        if not node:
            return True, None
        lu, lv = walk(node.left)
        ru, rv = walk(node.right)
        ok = (lu and ru
              and (lv is None or lv == node.val)
              and (rv is None or rv == node.val))
        if ok:
            count += 1
        return ok, node.val
    walk(root)
    return count

def lca(root, p, q):
    """Lowest common ancestor in a plain binary tree. O(n)."""
    if not root or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root            # p and q split here
    return left or right

def path_sum_all(root, target):
    """All root-to-leaf paths summing to target. Backtracking."""
    out, path = [], []
    def dfs(node, remaining):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            out.append(path[:])            # copy, path is mutated after
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)
        path.pop()                          # undo before returning
    dfs(root, target)
    return out

def serialize(root):
    """Preorder with explicit null markers."""
    out = []
    def go(n):
        if not n:
            out.append("#")
            return
        out.append(str(n.val))
        go(n.left)
        go(n.right)
    go(root)
    return ",".join(out)

def deserialize(data):
    vals = iter(data.split(","))
    def go():
        v = next(vals)
        if v == "#":
            return None
        node = TreeNode(int(v))
        node.left = go()
        node.right = go()
        return node
    return go()

def invert(root):
    if not root:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

// Java: the same postorder aggregation shape, using a field for the global
private int best = 0;
public int diameter(TreeNode root) { depth(root); return best; }
private int depth(TreeNode n) {
    if (n == null) return 0;
    int l = depth(n.left), r = depth(n.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
}