#226
Invert Binary Tree
Easy Swap children recursively
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Mirror a binary tree by swapping every node's left and right children.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: swap left and right everywhere.
Why this works: invert both subtrees, then swap them.
Example: 4 (2 (1, 3), 7 (6, 9))
→ 4 (7 (9, 6), 2 (3, 1))✦Hints open one at a time
Invert both subtrees, then swap them.
The order (swap first or recurse first) doesn't matter if you save references correctly.
↗Approach
Recursively invert left and right, then assign them crosswise.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left); // save both before assigning
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}!Common mistake
root.left = invert(root.right); root.right = invert(root.left); — the second line reads the already-changed left.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon