題目描述
給你兩棵二叉樹： root1 和 root2 境钟。
想象一下缺前，當(dāng)你將其中一棵覆蓋到另一棵之上時(shí)倔幼，兩棵樹上的一些節(jié)點(diǎn)將會(huì)重疊（而另一些不會(huì)）。你需要將這兩棵樹合并成一棵新二叉樹诫隅。合并的規(guī)則是：如果兩個(gè)節(jié)點(diǎn)重疊，那么將這兩個(gè)節(jié)點(diǎn)的值相加作為合并后節(jié)點(diǎn)的新值帐偎；否則逐纬，不為 null 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。
返回合并后的二叉樹削樊。
注意: 合并過(guò)程必須從兩個(gè)樹的根節(jié)點(diǎn)開始
示例1:
輸入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
輸出：[3,4,5,5,4,null,7]
示例 2：
輸入：root1 = [1], root2 = [1,2]
輸出：[2,2]
題解
思路1: 深度優(yōu)先搜索
可以使用深度優(yōu)先搜索合并兩個(gè)二叉樹豁生。從根節(jié)點(diǎn)開始同時(shí)遍歷兩個(gè)二叉樹，并將對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并漫贞。
兩個(gè)二叉樹的對(duì)應(yīng)節(jié)點(diǎn)可能存在以下三種情況甸箱，對(duì)于每種情況使用不同的合并方式。
- 如果兩個(gè)二叉樹的對(duì)應(yīng)節(jié)點(diǎn)都為空迅脐，則合并后的二叉樹的對(duì)應(yīng)節(jié)點(diǎn)也為空芍殖；
- 如果兩個(gè)二叉樹的對(duì)應(yīng)節(jié)點(diǎn)只有一個(gè)為空，則合并后的二叉樹的對(duì)應(yīng)節(jié)點(diǎn)為其中的非空節(jié)點(diǎn)谴蔑；
- 如果兩個(gè)二叉樹的對(duì)應(yīng)節(jié)點(diǎn)都不為空豌骏，則合并后的二叉樹的對(duì)應(yīng)節(jié)點(diǎn)的值為兩個(gè)二叉樹的對(duì)應(yīng)節(jié)點(diǎn)的值之和，此時(shí)需要顯性合并兩個(gè)節(jié)點(diǎn)隐锭。
對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行合并之后窃躲，還要對(duì)該節(jié)點(diǎn)的左右子樹分別進(jìn)行合并。這是一個(gè)遞歸的過(guò)程
func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
var mergeNode = TreeNode(root1!.val + root2!.val)
mergeNode.left = mergeTrees(root1!.left, root2!.left)
mergeNode.right = mergeTrees(root1!.right, root2!.right)
return mergeNode
}
思路2：廣度優(yōu)先搜索
也可以使用廣度優(yōu)先搜索合并兩個(gè)二叉樹钦睡。首先判斷兩個(gè)二叉樹是否為空蒂窒，如果兩個(gè)二叉樹都為空，則合并后的二叉樹也為空，如果只有一個(gè)二叉樹為空刘绣，則合并后的二叉樹為另一個(gè)非空的二叉樹樱溉。
如果兩個(gè)二叉樹都不為空，則首先計(jì)算合并后的根節(jié)點(diǎn)的值纬凤，然后從合并后的二叉樹與兩個(gè)原始二叉樹的根節(jié)點(diǎn)開始廣度優(yōu)先搜索福贞，從根節(jié)點(diǎn)開始同時(shí)遍歷每個(gè)二叉樹，并將對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并停士。
使用三個(gè)隊(duì)列分別存儲(chǔ)合并后的二叉樹的節(jié)點(diǎn)以及兩個(gè)原始二叉樹的節(jié)點(diǎn)挖帘。初始時(shí)將每個(gè)二叉樹的根節(jié)點(diǎn)分別加入相應(yīng)的隊(duì)列。每次從每個(gè)隊(duì)列中取出一個(gè)節(jié)點(diǎn)恋技，判斷兩個(gè)原始二叉樹的節(jié)點(diǎn)的左右子節(jié)點(diǎn)是否為空拇舀。如果兩個(gè)原始二叉樹的當(dāng)前節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，則合并后的二叉樹的對(duì)應(yīng)節(jié)點(diǎn)的左子節(jié)點(diǎn)也不為空蜻底。對(duì)于右子節(jié)點(diǎn)同理骄崩。
如果合并后的二叉樹的左子節(jié)點(diǎn)不為空，則需要根據(jù)兩個(gè)原始二叉樹的左子節(jié)點(diǎn)計(jì)算合并后的二叉樹的左子節(jié)點(diǎn)以及整個(gè)左子樹薄辅∫鳎考慮以下兩種情況：
如果兩個(gè)原始二叉樹的左子節(jié)點(diǎn)都不為空，則合并后的二叉樹的左子節(jié)點(diǎn)的值為兩個(gè)原始二叉樹的左子節(jié)點(diǎn)的值之和站楚，在創(chuàng)建合并后的二叉樹的左子節(jié)點(diǎn)之后脱惰，將每個(gè)二叉樹中的左子節(jié)點(diǎn)都加入相應(yīng)的隊(duì)列；
如果兩個(gè)原始二叉樹的左子節(jié)點(diǎn)有一個(gè)為空窿春，即有一個(gè)原始二叉樹的左子樹為空拉一，則合并后的二叉樹的左子樹即為另一個(gè)原始二叉樹的左子樹，此時(shí)也不需要對(duì)非空左子樹繼續(xù)遍歷旧乞，因此不需要將左子節(jié)點(diǎn)加入隊(duì)列蔚润。
對(duì)于右子節(jié)點(diǎn)和右子樹，處理方法與左子節(jié)點(diǎn)和左子樹相同良蛮。
func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
var rqueue = [TreeNode]()
var queue1 = [TreeNode]()
var queue2 = [TreeNode]()
let merged = TreeNode(root1!.val + root2!.val)
rqueue.append(merged)
queue1.append(root1!)
queue2.append(root2!)
while (!queue1.isEmpty && !queue2.isEmpty) {
let rnode = rqueue.removeFirst()
let node1 = queue1.removeFirst()
let node2 = queue2.removeFirst()
if node1.left != nil || node2.left != nil {
if node1.left != nil && node2.left != nil {
rnode.left = TreeNode(node1.left!.val + node2.left!.val)
rqueue.append(rnode.left!)
queue1.append(node1.left!)
queue2.append(node2.left!)
}else if node1.left != nil {
rnode.left = node1.left
}else {
rnode.left = node2.left
}
}
if node1.right != nil || node2.right != nil {
if node1.right != nil && node2.right != nil {
rnode.right = TreeNode(node1.right!.val + node2.right!.val)
rqueue.append(rnode.right!)
queue1.append(node1.right!)
queue2.append(node2.right!)
}else if node1.right != nil {
rnode.right = node1.right
}else {
rnode.right = node2.right
}
}
}
return merged
}
參考：https://leetcode-cn.com/problems/merge-two-binary-trees
https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
