Why it works
- The mirror of a tree is its root with the mirror of the right subtree on the left and the mirror of the left subtree on the right, so each call only needs its children's answers and one swap.
- A swap moves whole subtrees: when the root swaps, 2 moves right with 4 and 1, which were swapped earlier, so no node is ever swapped twice.
- Every node swaps its children exactly once, empty ones included, so nothing is left unmirrored.
Complexity
Time O(n): each node is visited once and does one swap. Memory O(h), where h is the height of the tree: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗