"""
Exercise 1: Same Tree (LeetCode 100)

Return True if two binary trees are structurally identical with equal values.
Recurse on both trees together.
"""

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

def is_same_tree(p, q):
    # TODO
    return False


# --- self-check: do not modify below this line ---
def build(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        n = q.pop(0)
        if i < len(level) and level[i] is not None:
            n.left = TreeNode(level[i]); q.append(n.left)
        i += 1
        if i < len(level) and level[i] is not None:
            n.right = TreeNode(level[i]); q.append(n.right)
        i += 1
    return root

cases = [([1, 2, 3], [1, 2, 3], True), ([1, 2], [1, None, 2], False), ([1, 2, 1], [1, 1, 2], False), ([], [], True)]
ok = True
for a, b, want in cases:
    got = is_same_tree(build(a), build(b))
    print(a, b, "->", got)
    ok = ok and got == want
print("PASS" if ok else "FAIL")