# recursively
def invertTree1(self, root):
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
# BFS
def invertTree2(self, root):
queue = collections.deque([(root)])
while queue:
node = queue.popleft()
if node:
node.left, node.right = node.right, node.left
queue.append(node.left)
queue.append(node.right)
return root
# DFS
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.extend([node.right, node.left])
return root
Python solutions (recursively, dfs, bfs).


@yabchexu Though it is 7 month later, I still reply you in case you still use leetcode. "Invert" for a node means switch its left child and right child instead of just switch its left child and right child's value.
So in this case, we first switch 4's left and right child, which results in [4,7,2,6,9,1,3]
And then switch 7 and 2's left/right child.