Recursively invert subtrees, then swap:
def invertTree(root):
if root == null:
return null
left = invertTree(root.left)
right = invertTree(root.right)
root.left = right
root.right = left
return root
Or swap first, then recurse—both work:
def invertTree(root):
if root == null:
return null
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
return root
Time: . Space: .
The order doesn't matter because swapping at one level is independent of swapping at other levels.