題目描述
給你兩棵二叉樹： root1 和 root2 。
想象一下，當(dāng)你將其中一棵覆蓋到另一棵之上時，兩棵樹上的一些節(jié)點(diǎn)將會重疊（而另一些不會）。你需要將這兩棵樹合并成一棵新二叉樹。合并的規(guī)則是：如果兩個節(jié)點(diǎn)重疊，那么將這兩個節(jié)點(diǎn)的值相加作為合并后節(jié)點(diǎn)的新值；否則，不為 null 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。
返回合并后的二叉樹。
注意: 合并過程必須從兩個樹的根節(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)先搜索合并兩個二叉樹。從根節(jié)點(diǎn)開始同時遍歷兩個二叉樹，并將對應(yīng)的節(jié)點(diǎn)進(jìn)行合并。
兩個二叉樹的對應(yīng)節(jié)點(diǎn)可能存在以下三種情況，對于每種情況使用不同的合并方式。
- 如果兩個二叉樹的對應(yīng)節(jié)點(diǎn)都為空，則合并后的二叉樹的對應(yīng)節(jié)點(diǎn)也為空；
- 如果兩個二叉樹的對應(yīng)節(jié)點(diǎn)只有一個為空，則合并后的二叉樹的對應(yīng)節(jié)點(diǎn)為其中的非空節(jié)點(diǎn)；
- 如果兩個二叉樹的對應(yīng)節(jié)點(diǎn)都不為空，則合并后的二叉樹的對應(yīng)節(jié)點(diǎn)的值為兩個二叉樹的對應(yīng)節(jié)點(diǎn)的值之和，此時需要顯性合并兩個節(jié)點(diǎn)。
對一個節(jié)點(diǎn)進(jìn)行合并之后，還要對該節(jié)點(diǎn)的左右子樹分別進(jìn)行合并。這是一個遞歸的過程
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)先搜索合并兩個二叉樹。首先判斷兩個二叉樹是否為空，如果兩個二叉樹都為空，則合并后的二叉樹也為空，如果只有一個二叉樹為空，則合并后的二叉樹為另一個非空的二叉樹。
如果兩個二叉樹都不為空，則首先計算合并后的根節(jié)點(diǎn)的值，然后從合并后的二叉樹與兩個原始二叉樹的根節(jié)點(diǎn)開始廣度優(yōu)先搜索，從根節(jié)點(diǎn)開始同時遍歷每個二叉樹，并將對應(yīng)的節(jié)點(diǎn)進(jìn)行合并。
使用三個隊列分別存儲合并后的二叉樹的節(jié)點(diǎn)以及兩個原始二叉樹的節(jié)點(diǎn)。初始時將每個二叉樹的根節(jié)點(diǎn)分別加入相應(yīng)的隊列。每次從每個隊列中取出一個節(jié)點(diǎn)，判斷兩個原始二叉樹的節(jié)點(diǎn)的左右子節(jié)點(diǎn)是否為空。如果兩個原始二叉樹的當(dāng)前節(jié)點(diǎn)中至少有一個節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，則合并后的二叉樹的對應(yīng)節(jié)點(diǎn)的左子節(jié)點(diǎn)也不為空。對于右子節(jié)點(diǎn)同理。
如果合并后的二叉樹的左子節(jié)點(diǎn)不為空，則需要根據(jù)兩個原始二叉樹的左子節(jié)點(diǎn)計算合并后的二叉樹的左子節(jié)點(diǎn)以及整個左子樹?？紤]以下兩種情況：
如果兩個原始二叉樹的左子節(jié)點(diǎn)都不為空，則合并后的二叉樹的左子節(jié)點(diǎn)的值為兩個原始二叉樹的左子節(jié)點(diǎn)的值之和，在創(chuàng)建合并后的二叉樹的左子節(jié)點(diǎn)之后，將每個二叉樹中的左子節(jié)點(diǎn)都加入相應(yīng)的隊列；
如果兩個原始二叉樹的左子節(jié)點(diǎn)有一個為空，即有一個原始二叉樹的左子樹為空，則合并后的二叉樹的左子樹即為另一個原始二叉樹的左子樹，此時也不需要對非空左子樹繼續(xù)遍歷，因此不需要將左子節(jié)點(diǎn)加入隊列。
對于右子節(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/
