226. Invert Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 67.3%
Problem Breakdown
The problem requires us to invert a binary tree. Given the root of a binary tree, we need to swap every left child with its corresponding right child throughout the entire tree and return the root of the inverted tree.
Inputs:
root: The root node of the binary tree.
Outputs:
- The root node of the inverted binary tree.
Implicit Constraints or Tricky Edge Cases:
- An empty tree (i.e.,
rootisnull). - A tree with only one node.
- Trees where all nodes have both left and right children.
Intuition
A brute-force approach would involve traversing each node in the tree and manually swapping its left and right children. However, this approach is inefficient because it doesn’t take advantage of the recursive nature of trees.
The key insight is to use a recursive approach to invert the tree. By recursively inverting the left and right subtrees and then swapping them at each node, we can achieve the desired inversion efficiently.
Approach
We will use a recursive depth-first search (DFS) approach to traverse the tree. At each node, we:
- Recursively invert its left subtree.
- Recursively invert its right subtree.
- Swap the left and right children of the current node.
- Return the root node of the inverted tree.
This approach ensures that every node in the tree is visited once, and its children are swapped correctly.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), the space complexity can be O(n).
Solution
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 root is None:
return None
# Recursively invert the left and right subtrees
left_inverted = invertTree(root.left)
right_inverted = invertTree(root.right)
# Swap the left and right children
root.left = right_inverted
root.right = left_inverted
return root
Edge Cases Handled
- Empty Tree: If the input tree is empty (
rootisNone), the function immediately returnsNone, which is correct for an inverted empty tree. - Single Node Tree: A tree with only one node remains unchanged after inversion since it has no children to swap.
- Skewed Trees: The recursive approach handles skewed trees (completely unbalanced) efficiently, as each node is processed in constant time.