Invert Binary Tree
Invert Binary Tree is an easy Trees problem from the Blind 75. The key pattern is tree recursion, and a good solution runs in O(n) time.
Problem
Mirror a level-order binary tree by swapping every node's left and right children; preserve null placeholders and trim trailing nulls.
Examples
Example 1
Input
[8,4,12,2,6,10,14]Output
[8,12,4,14,10,6,2]Example 2
Input
[7,5,9]Output
[7,9,5]Example 3
Input
[]Output
[]Approach
Swap each node's left and right children, then do the same for both subtrees.
| Pattern | Tree recursion |
|---|---|
| Time | O(n) |
| Space | O(h) |
Watch out for
An empty tree inverts to an empty tree.