プロンプト
Claude, invert a binary tree in Python
回答
Invert a Binary Tree in Python
Here's a solution with both recursive and iterative approaches:
Recursive Approach (Simplest)
PYTHON
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
"""Invert a binary tree recursively."""
if not root:
return None
# Swap left and right children
root.left, root.right = root.right, root.left
# Recursively invert left and right subtrees
invertTree(root.left)
invertTree(root.right)
return root
Iterative Approach (Using a Queue)
PYTHON
from collections import deque
def invertTree(root):
"""Invert a binary tree iteratively using BFS."""
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
# Swap left and right children
node.left, node.right = node.right, node.left
# Add children to queue for processing
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
Example Usage
PYTHON
# Create a sample tree:
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
invertTree(root)
# Result after inversion:
# 1
# / \
# 3 2
Complexity Analysis
- Time Complexity: O(n) — visit each node once
- Space Complexity:
- Recursive: O(h) where h is height (call stack)
- Iterative: O(w) where w is max width (queue size)
Recommendation: Use the recursive approach for simplicity and readability. It's elegant and handles the problem naturally.
Haiku 4.5の回答
