LeetCode 226 · Trees · concept: trees
Problem
Invert a binary tree — mirror it so every node’s left and right children swap.
4 4
2 7 -> 7 2
1 3 6 9 9 6 3 1
Approach — recursive swap (optimal)
Swap the current node’s children, then recurse into both. The whole solution is three lines because the tree’s structure is the recursion.
def invertTree(root):
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootTime O(n) (visit each node once), space O(h) for the recursion stack (h = height; O(log n) balanced, O(n) skewed).
An iterative BFS/DFS with a queue/stack does the same, swapping children as you pop — useful if recursion depth is a concern.
Key insight
Most binary-tree problems are “do something at this node, then recurse into both subtrees.” Invert is the minimal example of that shape — the base case (None) plus a per-node action plus two recursive calls. Internalize this skeleton; nearly every tree problem below reuses it.
Related
- concept: trees, dfs
- next: Maximum Depth of Binary Tree
Software engineering
Infrastructure & security
Computer science
Hardware & engineering