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