leetcode226. 翻轉(zhuǎn)二叉樹
翻轉(zhuǎn)一棵二叉樹。
示例：
輸入：
? ? 4
? /? \
? 2? ? 7
/ \? / \
1? 3 6? 9
輸出：
? ? 4
? /? \
? 7? ? 2
/ \? / \
9? 6 3? 1
（1）遞歸寫法：
關(guān)鍵點是對換當(dāng)前根節(jié)點的左右節(jié)點和遞歸當(dāng)前根節(jié)點的左右節(jié)點：
class?Solution:
????def?invertTree(self,?root:?TreeNode)?->?TreeNode:
????????if?not?root:
????????????return?
? ? ? ? tmp=root.left
????????root.left=root.right
????????root.right=tmp
????????self.invertTree(root.left)?
????????self.invertTree(root.right)
????????return?root
（2）迭代寫法
關(guān)鍵點：對換節(jié)點和不斷引入右左節(jié)點，以及每次遍歷一層，寬度優(yōu)先遍歷
class?Solution:
????def?invertTree(self,?root:?TreeNode)?->?TreeNode:
????????if?not?root:
????????????return?
????????d1=[root]
????????while?d1:
????????????for?i?in?range(len(d1)):
????????????????t=d1.pop(0)
????????????????tmp=t.right
????????????????t.right=t.left
????????????????t.left=tmp
????????????????if?t.left:
????????????????????d1.append(t.left)
????????????????if?t.right:
????????????????????d1.append(t.right)
????????return?root
leetcode617. 合并二叉樹
給定兩個二叉樹，想象當(dāng)你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節(jié)點便會重疊。
你需要將他們合并為一個新的二叉樹。合并的規(guī)則是如果兩個節(jié)點重疊，那么將他們的值相加作為節(jié)點合并后的新值，否則不為?NULL 的節(jié)點將直接作為新二叉樹的節(jié)點。
示例?1:
輸入:
Tree 1? ? ? ? ? ? ? ? ? ? Tree 2? ? ? ? ? ? ? ? ?
? ? ? ? ? 1? ? ? ? ? ? ? ? ? ? ? ? 2? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? / \? ? ? ? ? ? ? ? ? ? ? / \? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? 3? 2? ? ? ? ? ? ? ? ? ? 1? 3? ? ? ? ? ? ? ? ? ? ? ?
? ? ? /? ? ? ? ? ? ? ? ? ? ? ? ? \? \? ? ? ? ? ? ? ? ? ? ?
? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? ? ? 4? 7? ? ? ? ? ? ? ? ?
輸出:
合并后的樹:
? ? 3
? ? / \
? 4? 5
? / \? \
5? 4? 7
注意:?合并必須從兩個樹的根節(jié)點開始。
(1)遞歸寫法
關(guān)鍵點是比較節(jié)點和遞歸左右節(jié)點
代碼如下：
class?Solution:
????def?mergeTrees(self,?t1:?TreeNode,?t2:?TreeNode)?->?TreeNode:
????????t=TreeNode()?????
????????if?not?t1?and?not?t2:
????????????return???????
????????if?not?t1?or?not?t2:
????????????if??t1:
????????????????t=t1
????????????if??t2:
????????????????t=t2??????
????????if??t1?and?t2:
????????????t.val=t1.val+t2.val
????????????t.left=self.mergeTrees(t1.left,t2.left)
????????????t.right=self.mergeTrees(t1.right,t2.right)??????
????????return?t
（2）迭代寫法
關(guān)鍵點：
1）一個隊列的元素中包含左右樹，先進行值加操作，確定都不為空添加，然后為空時如下：
2）判斷左樹為空，將右樹值賦給左樹
class?Solution:
????def?mergeTrees(self,?t1:?TreeNode,?t2:?TreeNode)?->?TreeNode:
????????if?not?(t1?and?t2):
????????????if?not?t1:
????????????????return?t2
????????????if?not?t2:
????????????????return?t1
????????queue?=?[(t1,t2)]
????????while?queue:
????????????r1,r2?=?queue.pop(0)
????????????r1.val?+=?r2.val
????????????#?如果r1和r2的左子樹都不為空，就放到隊列中
????????????#?如果r1的左子樹為空，就把r2的左子樹掛到r1的左子樹上
????????????if?r1.left?and?r2.left:
????????????????queue.append((r1.left,r2.left))
????????????elif?not?r1.left:
????????????????r1.left?=?r2.left
????????????#?對于右子樹也是一樣的
????????????if?r1.right?and?r2.right:
???????????????queue.append((r1.right,r2.right))
????????????elif?not?r1.right:
????????????????r1.right?=?r2.right
????????return?t1
