アルゴリズム_2 つのバイナリツリーのマージ#
2 つのバイナリツリー、root1 と root2 が与えられます。
片方のツリーをもう一方の上に配置した場合、2 つのツリーの一部のノードは重なり、他のノードは重なりません。2 つのツリーを新しいバイナリツリーにマージする必要があります。マージのルールは、2 つのノードが重なる場合、重なるノードの値を合計してマージされたノードの新しい値とします。それ以外の場合、null でないノードが新しいツリーのノードとして使用されます。
マージされたツリーを返します。
注意：マージのプロセスは両方のツリーのルートノードから開始する必要があります。
例 1：
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
例 2：
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
解法#
再帰を使用します。上記の例からわかるように、基本的な計算は 2 つの値を合計することです。1 つが null の場合は 0 と合計します。
コードのロジック：
新しい TreeNode を宣言し、TreeNode の val は root1.val + root2.val、TreeNode の left は再帰 (root1.left, roo2.left)、right は再帰 (root1.right, root2.right) です。
以下はコードです：
/**
* Definition for a binary tree node.
* 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
}
}