## Description

Invert a binary tree.

Example:

Input:

     4
/   \
2     7
/ \   / \
1   3 6   9


Output:

     4
/   \
7     2
/ \   / \
9   6 3   1


Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

## Solutions

将二叉树翻转得到镜像结果。

### 1. DFS-Recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# DFS-Recursion
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
left, right = root.left, root.right

root.right = self.invertTree(left)
root.left = self.invertTree(right)
return root

# 68/68 cases passed (28 ms)
# Your runtime beats 67.8 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)


或者：

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.right, root.left = root.left, root.right

self.invertTree(root.left)
self.invertTree(root.right)
return root
# 68/68 cases passed (28 ms)
# Your runtime beats 67.73 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)


更简洁版：

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)
return root

# 68/68 cases passed (24 ms)
# Your runtime beats 89.08 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)


### 2. DFS-Iterative

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
node.right, node.left = node.left, node.right
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root

# 68/68 cases passed (20 ms)
# Your runtime beats 97.49 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)


### 3. BFS-Iterative

# BFS-Recursion
import collections
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
node.right, node.left = node.left, node.right
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root

# 68/68 cases passed (24 ms)
# Your runtime beats 89.08 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)