アルゴリズム_二つの二分木をマージする#
二つの二分木 root1 と root2 が与えられます。
一方を他方に重ねると、一部のノードが重なり、他のノードは重ならないことを想像してください。二つの木を新しい二分木にマージする必要があります。マージのルールは、二つのノードが重なる場合、ノードの値を合計してマージされたノードの新しい値とします。そうでない場合は、NULL でないノードが新しい木のノードとして使用されます。
マージされた木を返します。
注意：マージプロセスは、両方の木のルートノードから始める必要があります。
例 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]
解法#
再帰を使用します。上の例からわかるように、基本的な計算は二つの値を加算することです。一方が NULL の場合は、0 と加算します。
コードのロジック：
新しい TreeNode を宣言し、TreeNode の val = root1.val + root2.val、TreeNode の left = 再帰 (root1.left, root2.left)、right = 再帰 (root1.right, root2.right)
コードは以下の通りです：
/**
* 二分木ノードの定義。
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init() { self.val = 0; self.left = nil; self.right = nil; }
* public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
* public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
* self.val = val
* self.left = left
* self.right = right
* }
* }
*/
class Solution {
func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
if root1 == nil && root2 == nil {
return nil
}
let valValue = (root1 == nil ? 0 : root1!.val) + (root2 == nil ? 0 : root2!.val)
let newNode = TreeNode(valValue)
newNode.left = mergeTrees(root1?.left, root2?.left)
newNode.right = mergeTrees(root1?.right, root2?.right)
return newNode
}
}