## 题目描述：

Invert a binary tree.

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

to

```     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 fuck off.

## Python代码（递归版本）：

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {TreeNode}
def invertTree(self, root):
if root is None:
return None
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
``````

## Python代码（迭代版本）：

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {TreeNode}
def invertTree(self, root):
if root is None:
return None
queue = [root]
while queue:
front = queue.pop(0)
if front.left:
queue.append(front.left)
if front.right:
queue.append(front.right)
front.left, front.right = front.right, front.left
return root
``````

Pingbacks已关闭。