翻轉(zhuǎn)一棵二叉樹。
示例：
輸入：
? ? 4
? /? \
? 2? ? 7
/ \? / \
1? 3 6? 9
輸出：
? ? 4
? /? \
? 7? ? 2
/ \? / \
9? 6 3? 1
第一種思路：
遞歸+交換左右子樹+保留最初的樹
代碼如下：
#?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:
????????if?not?root:
????????????return?root
????????tmp0=root
????????tmp=root.right
????????root.right=root.left
????????root.left=tmp
????????self.invertTree(root.right)
????????self.invertTree(root.left)
????????return?tmp0
第二種思路：迭代+深度優(yōu)先，用廣度優(yōu)先搜索的方法來進行解題，將每一層的字?jǐn)?shù)加入到stack中，然后對每一個子樹的左右子樹進行交換
class?Solution:
????def?invertTree(self,?root:?TreeNode)?->?TreeNode:
????????if?not?root?:?return?
????????stack?=?[root]
????????while?stack?:
????????????length?=?len(stack)
????????????for?i?in?range(length):
????????????????cur?=?stack.pop(0)
????????????????cur.left,cur.right?=?cur.right,cur.left
????????????????if?cur.left?:
????????????????????stack.append(cur.left)
????????????????if?cur.right?:
????????????????????stack.append(cur.right)
????????return?root
