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


#-----------树 基础--------------

def traverse(root):
    if not root:
        return

    q = list()
    q.append(root)
    while len(q) > 0:
        node = q.pop(0)
        if not node:
            continue
        print(node.val)
        q.append(node.left)
        q.append(node.right)

def recur_preorder(root):
    if not root:
        return
    print(root.val)
    recur_preorder(root.left)
    recur_preorder(root.right)

def recur_inorder(root):
    if not root:
        return
    recur_inorder(root.left)
    print(root.val)
    recur_inorder(root.right)

def recur_postorder(root):
    if not root:
        return
    recur_postorder(root.left)
    recur_postorder(root.right)
    print(root.val)


def is_same_tree(root1, root2):
    # 都到最后叶子节点，相同
    if not root1 and not root2:
        return True

    if (not root1) or (not root2):
        return False

    if root1.val != root2.val:
        return False

    return is_same_tree(root1.left, root2.left) and is_same_tree(root1.right, root2.right)