Description
給定兩棵二元樹，將它們合併成一棵新樹。合併規則：若兩個節點重疊，則將它們的值相加；若只有一方有節點，則使用該節點。
Example:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]
Intuition#
同時遍歷兩棵樹，對應位置的節點值相加，遞迴合併左右子樹。
- 若其中一棵為 null，直接回傳另一棵
- 若兩棵都存在，建立新節點（值相加），遞迴處理左右子樹
Approaches#
⭐ 1: Recursive DFS#
- 概念: 同時遞迴兩棵樹，合併對應節點
- 時間複雜度:
O(min(m, n))，m、n 為兩棵樹的節點數，只遍歷重疊部分 - 空間複雜度:
O(min(h1, h2))，遞迴深度取決於較矮的樹
class Solution {
fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
if (root1 == null) return root2
if (root2 == null) return root1
val merged = TreeNode(root1.`val` + root2.`val`)
merged.left = mergeTrees(root1.left, root2.left)
merged.right = mergeTrees(root1.right, root2.right)
return merged
}
}2: Iterative BFS#
- 概念: 使用佇列同時遍歷兩棵樹，直接修改第一棵樹
- 時間複雜度:
O(min(m, n)) - 空間複雜度:
O(min(m, n))
class Solution {
fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
if (root1 == null) return root2
if (root2 == null) return root1
val queue = ArrayDeque<Pair<TreeNode, TreeNode>>()
queue.add(root1 to root2)
while (queue.isNotEmpty()) {
val (n1, n2) = queue.removeFirst()
n1.`val` += n2.`val`
if (n1.left != null && n2.left != null) {
queue.add(n1.left!! to n2.left!!)
} else if (n1.left == null) {
n1.left = n2.left
}
if (n1.right != null && n2.right != null) {
queue.add(n1.right!! to n2.right!!)
} else if (n1.right == null) {
n1.right = n2.right
}
}
return root1
}
}🔑 Takeaways#
- Pattern: 同時遍歷兩棵樹 — 對應節點配對處理
- 關鍵技巧: 處理兩棵樹的問題時，null 檢查是關鍵：一方為 null 時直接回傳另一方