def transpose(root):
    if root is None:
        return
    if root.left is None and root.right is None:
        return
    root.left, root.right = root.right, root.left
    if root.left is not None:
        transpose(root.left)
    if root.right is not None:
        transpose(root.right)
    return root

def transpose_(root):
    stack = []
    if root is not None:
        stack.append(root)
        while len(stack) != 0:
            temp = stack.pop()
            temp.left, temp.right = temp.right, temp.left
            if temp.left is not None:
                stack.append(temp.left)
            if temp.right is not None:
                stack.append(temp.right)

    return root