Invert Binary Tree
Given the `root` of a binary tree, invert the tree (mirror it left-to-right) and return its root. **Core Insight:** To invert a binary tree, swap the left and right children of every node. This is naturally recursive: invert the left subtree, invert the right subtree, then swap the two children at the current node. The base case is a null node — nothing to do. **Algorithm (recursive):** If `root` is null return null. Recursively call `invertTree(root.left)` and `invertTree(root.right)`. Then swap: `root.left, root.right = root.right, root.left`. Return `root`. **Algorithm (iterative BFS):** Use a queue. For each dequeued node, swap its children and enqueue both non-null children. **Why post-order works:** We can also swap first then recurse (pre-order) — both are correct because swapping at any order produces the same mirrored result. **Complexity:** Time O(n) — every node is visited once. Space O(h) for recursion (h = tree height), O(n) worst case for a completely skewed tree.
Constraints
- •
The number of nodes in the tree is in the range [0, 100] - •
-100 ≤ Node.val ≤ 100
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root