617.合并二叉樹(shù)（經(jīng)典）

合并二叉樹(shù)是操作兩棵樹(shù)的題目里面很經(jīng)典的，如何對(duì)兩棵樹(shù)遍歷以及處理？
給定兩個(gè)二叉樹(shù)，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)，兩個(gè)二叉樹(shù)的一些節(jié)點(diǎn)便會(huì)重疊。
你需要將他們合并為一個(gè)新的二叉樹(shù)。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹(shù)的節(jié)點(diǎn)。
示例 1:

注意: 合并必須從兩個(gè)樹(shù)的根節(jié)點(diǎn)開(kāi)始。

思路

參考：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
如何同時(shí)遍歷兩個(gè)二叉樹(shù)呢？
其實(shí)和遍歷一個(gè)樹(shù)邏輯是一樣的，只不過(guò)傳入兩個(gè)樹(shù)的節(jié)點(diǎn)，同時(shí)操作。

遞歸

二叉樹(shù)使用遞歸，就要想使用前中后哪種遍歷方式？
本題使用哪種遍歷都是可以的！
我們下面以前序遍歷為例。

1. 確定遞歸函數(shù)的參數(shù)和返回值：

首先要合入兩個(gè)二叉樹(shù)，那么參數(shù)至少是要傳入兩個(gè)二叉樹(shù)的根節(jié)點(diǎn)，返回值就是合并之后二叉樹(shù)的根節(jié)點(diǎn)。

2. 因?yàn)槭莻魅肓藘蓚€(gè)樹(shù)，那么就有兩個(gè)樹(shù)遍歷的節(jié)點(diǎn)t1 和 t2，如果t1 == NULL 了，兩個(gè)樹(shù)合并就應(yīng)該是 t2 了（如果t2也為NULL也無(wú)所謂，合并之后就是NULL）。

反過(guò)來(lái)如果t2 == NULL，那么兩個(gè)數(shù)合并就是t1（如果t1也為NULL也無(wú)所謂，合并之后就是NULL）。

3. 確定單層遞歸的邏輯：

單層遞歸的邏輯就比較好寫(xiě)了，這里我們重復(fù)利用一下t1這個(gè)樹(shù)，t1就是合并之后樹(shù)的根節(jié)點(diǎn)（就是修改了原來(lái)樹(shù)的結(jié)構(gòu)）。
那么單層遞歸中，就要把兩棵樹(shù)的元素加到一起。
接下來(lái)t1 的左子樹(shù)是：合并 t1左子樹(shù) t2左子樹(shù)之后的左子樹(shù)。
t1 的右子樹(shù)：是 合并 t1右子樹(shù) t2右子樹(shù)之后的右子樹(shù)。
最終t1就是合并之后的根節(jié)點(diǎn)。

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def mergeTrees(self, root1, root2): # 傳入?yún)?shù) 就是兩棵樹(shù) 這里以根節(jié)點(diǎn)表示""":type root1: TreeNode:type root2: TreeNode:rtype: TreeNode"""# 遍歷兩棵樹(shù) 與遍歷一棵樹(shù)的邏輯是一樣的 這里采用前序遍歷的方式if not root1:return root2if not root2:return root1# 中 中的處理邏輯就是節(jié)點(diǎn)的值相加root1.val += root2.val # 根節(jié)點(diǎn)更新(以root1表示更新之后的樹(shù))# 左root1.left = self.mergeTrees(root1.left, root2.left)# 右root1.right = self.mergeTrees(root1.right, root2.right)return root1# 當(dāng)然 也可以新建節(jié)點(diǎn) 比如 root

迭代法

# 法二 迭代法 需要模擬隊(duì)列來(lái)存儲(chǔ)兩棵樹(shù)上的節(jié)點(diǎn) 這樣就是層序遍歷
from collections import deque
class Solution(object):def mergeTrees(self, root1, root2):if not root1:return root2if not root2:return root1queue = deque()queue.append(root1)queue.append(root2)while queue: # 以root1為更新之后的樹(shù)# 彈出節(jié)點(diǎn)node1 = queue.popleft()node2 = queue.popleft()# 左if node1.left and node2.left: # 兩邊左節(jié)點(diǎn)都存在queue.append(node1.left)queue.append(node2.left)# 右if node1.right and node2.right: # 兩邊右節(jié)點(diǎn)都存在queue.append(node1.right)queue.append(node2.right)# 更新當(dāng)前節(jié)點(diǎn). 同時(shí)改變當(dāng)前節(jié)點(diǎn)的左右孩子. node1.val += node2.valif not node1.left and node2.left: # node1無(wú)左節(jié)點(diǎn) 那就用node2的 node2沒(méi)用也沒(méi)事 就是Nullnode1.left = node2.leftif not node1.right and node2.right:node1.right = node2.rightreturn root1