Invert Binary Tree
You get the root of a binary tree. Invert it: at every node, swap the left and right children. Return the root of the inverted tree.
The tree is written in level order, with null for a missing child.
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 value <= 100
Stuck? Take one hint at a time
Common mistakes
- Swapping the values of the nodes instead of swapping the children, which does not mirror the shape.
- Swapping only at the root and forgetting to invert the subtrees.
- Swapping a node's children and then swapping them again after the recursive calls, which undoes the work.
- Not returning the root, so the caller gets nothing back.
Questions an interviewer may ask next
- Check whether a tree is symmetric: its left side is a mirror of its right side. (Compare a tree with its mirror, in lockstep.)
- Invert only the nodes at even depth.
- Return a new inverted tree and leave the original unchanged. What does the recursion return then?
- How many swaps does the inversion perform? (One per non-leaf node.)
root
[4,2,7,1,3,6,9]
Expected output
[4,7,2,9,6,3,1]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.