題目
翻轉一棵二叉樹。
示例：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
備注:
這個問題是受到 Max Howell 的 原問題 啟發(fā)的 ：
谷歌：我們90％的工程師使用您編寫的軟件(Homebrew)为黎，但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題牵舵，這太糟糕了孵淘。
解題思路
廣度優(yōu)先搜索姨蟋，深度優(yōu)先搜索
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
##深度優(yōu)先
# if root:
# temp = root.left
# root.left = root.right
# root.right = temp
# root.left = self.invertTree(root.left)
# root.right = self.invertTree(root.right)
# return root;
# else:
# return None
##廣度優(yōu)先召噩，用堆棧來處理
if root:
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
else:
return None
