23. Merge Two Binary Trees

読了目安約1分

Tree / LC 617 (Easy) — 2 つの木を重ねて値を足す。同時再帰の練習。

この章の目次

問題

LeetCode 617. Merge Two Binary Trees（Easy / カテゴリ: Tree）

2 つの二分木の根 root1 と root2 が与えられます。 2 つの木を同じ位置で重ね合わせた木を返します。両方にノードがある位置は値の和、片方にしか無い位置はそのノードをそのまま使います。

考え方

ヒント 1

2 つの木を根から同時にたどります。「両方 nil」「片方だけ nil」「両方ある」の 3 通りを考えます。

ヒント 2

片方が nil なら、もう片方の部分木をそのまま返して打ち切れます。両方あるときは値の和で新しいノードを作り、左同士・右同士を再帰でマージして子につなぎます。

Swift 実装のポイント

guard let r1 = root1 else { return root2 } を 2 回書くと、「片方が nil」の処理が 2 行で済みます。
両方 nil のときも最初の guard が root2（= nil）を返すので、特別扱いは不要です。
入力の木を書き換える解もありますが、新しいノードを作る実装は入力を壊さないので安全です。

模範解答

Swift
class Solution {
    func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
        guard let r1 = root1 else { return root2 }
        guard let r2 = root2 else { return root1 }
        let node = TreeNode(r1.val + r2.val)
        node.left = mergeTrees(r1.left, r2.left)
        node.right = mergeTrees(r1.right, r2.right)
        return node
    }
}

計算量: O(min(N1, N2))。両方の木に存在する位置だけを訪れます。