Part 2 · Problems · Trees and BFS
Invert Binary Tree
#226 · Easy · LeetCode
Mirror the tree: swap every node's left and right children.
[4,2,7,1,3,6,9] -> [4,7,2,9,6,3,1]
Ask before coding
- In place OK?
Hint
Swap at the root, then do the same for each child.
Approach
Recursively invert both children and assign them swapped.
Time O(n) Space O(h)
Watch it run
Solution (JavaScript, tested)
function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}Traps
- Swapping then recursing into the 'wrong' side if you reuse old variables.
Say out loud: Each node does the same small job, swap children, so recursion fits.