Invert Binary Tree

Share

Given the root of a binary tree, invert the tree (mirror it), and return its root.

Example 1
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2
Input: root = [2,1,3]
Output: [2,3,1]
Example 3
Input: root = []
Output: []
Constraints:

Contents

Solution 1: Recursive DFS

To invert a tree: swap the left and right children of the current node, then recursively invert each subtree.

Java
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    // Swap left and right children
    TreeNode temp = root.left;
    root.left  = root.right;
    root.right = temp;

    // Recursively invert subtrees
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

Solution 2: Iterative BFS

Use a queue to process nodes level by level; swap children at each node.

Java
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();

        // Swap children
        TreeNode temp = node.left;
        node.left  = node.right;
        node.right = temp;

        if (node.left  != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return root;
}

Complexity Analysis