The problem
A binary tree is made of nodes, each holding a value and at most two children, left and right; the top node is the root. Here a tree is written level by level, left to right, with null for a missing child.
Given the root, mirror the tree — swap every node’s left and right children, all the way down — and return its root.
Examples
- Input
root = [4, 2, 7, 1, 3, 6, 9]
- Output
[4, 7, 2, 9, 6, 3, 1]
- Input
root = [2, 1, 3]
- Output
[2, 3, 1]
- Input
root = []
- Output
[]
Constraints
- 0 ≤ number of nodes ≤ 100
- −100 ≤ Node.val ≤ 100
The idea
The mirror of a tree is: the same root, with the mirror of its right subtree on the left and the mirror of its left subtree on the right.
That sentence is the code. Recursion — a function calling itself on a smaller piece — does the rest: each call swaps one node’s children and trusts the calls below to mirror theirs. An empty tree is its own mirror, which stops it.
- Time
- O(n) — each node is swapped once
- Space
- O(h) — the calls waiting on the way down, h the tree’s height
Solution · every language run against every case
class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root: # Swap the children, then mirror each of them the same way. root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root