Easy

Invert Binary Tree

015

Given a binary tree encoded as level-order with -100000 as null, return the inverted tree in level-order using the same encoding.

EXAMPLES

Example 1

Input
{
  "root": [
    4,
    2,
    7,
    1,
    3,
    6,
    9
  ]
}

Output
[
  4,
  7,
  2,
  9,
  6,
  3,
  1
]

FUNCTION SHAPE

root: intArray→intArray

SOLUTION NOTE

We don't just swap values - the ENTIRE subtree is swapped. This can be written in preorder, inorder, or postorder!

Reveal reference solution +

pythonREFERENCE

# Preorder solution
def invertTree(self, root: TreeNode) -> TreeNode:
    if not root:
        return None

    # Swap children FIRST (preorder)
    root.left, root.right = root.right, root.left

    # Recursively invert subtrees
    self.invertTree(root.left)
    self.invertTree(root.right)

    return root

# Postorder solution
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root: return root
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root

TimeO(n)

SpaceO(h)

Open on LeetCode ↗