Given the root of a binary tree, mirror it: every node's left and right children swap, all the way down. Return the root. A TreeNode has an int val and left/right children (null where absent); TreeNode(val) creates one, though inversion needs no new nodes.
Examples
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 = [1]
Output: [1]
Example 4:
Input: root = []
Output: []
Constraints
0 <= number of nodes <= 100
-100 <= Node.val <= 100
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. Swap the Children, Recurse Optimal
Intuition
Mirroring a tree is swapping every node's children — and a node's own subtrees are just smaller trees to mirror. Recursion writes itself: swap here, invert both sides, and the empty tree is the base case that needs no thought.
Algorithm
1. An empty tree inverts to itself. 2. Invert the left subtree and the right subtree. 3. Attach them to the opposite sides. 4. Return the node.
Time & Space
Time O(n) — each node visited once. Space O(h) for the call stack, h being the height.