【LeetCode】617. Merge Two Binary Trees 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python,再帰(recursion)
2. 解答2:
補足・参考・感想

問題

原文

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]

1
2

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2] Output: [2,2]

1
2

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

The number of nodes in both trees is in the range [0, 2000].

-10⁴ <= Node.val <= 10⁴

内容

2つの二分木root1,root2が与えられます。

片方の木をもう片方の木に被せると、いくつかのノードは重なり、残りは重なりません。

二つの木を新しい二分木に結合してください。

結合ルールは、もし二つのノードが重なればそのノードの値を合計し新しいノードの値とします。

二つのノードが重ならない場合は、NOT nullノードが新しい木のノードとして使用されます。

結合後の木を返してください。

・補足

2つの木を重ねたときに、3つのパターンがあります。

➀2つともノードがある場合

②片方だけノードがある場合

③2つともノードがない場合

➀はノードの値を合計する

②は片方のノードの値をそのまま使う

③は何もしない

※正しくない可能性があります。

解答

解答1：Python,再帰(recursion)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        #root1,root2のどちらもNoneでない場合
        if root1 and root2:
            #rootをTreeNodeのインスタンス、つまり二分木の親として作成し、その値はroot1,root2の値の合計値にする
            root = TreeNode(root1.val + root2.val)
            #二分木の親であるrootの左右の子ノードで再帰的に関数を呼び出し、同様の操作を行う。
            root.left = self.mergeTrees(root1.left, root2.left)
            root.right = self.mergeTrees(root1.right, root2.right)
            #葉ノードまで同じことを繰り返す。葉ノードでは左右の子ノードがないのrootだけを返す
            return root
        #root1かroo2のどちらか、もしくは両方がNoneの場合
        else:
            #root1かroot2をそのまま返す。少なくとも片方はNoneなので、どちらかの値か、Noneが返される。
            return root1 or root2

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:

#root1,root2のどちらもNoneでない場合

if root1 and root2:

#rootをTreeNodeのインスタンス、つまり二分木の親として作成し、その値はroot1,root2の値の合計値にする

root = TreeNode(root1.val + root2.val)

#二分木の親であるrootの左右の子ノードで再帰的に関数を呼び出し、同様の操作を行う。

root.left = self.mergeTrees(root1.left, root2.left)

root.right = self.mergeTrees(root1.right, root2.right)

#葉ノードまで同じことを繰り返す。葉ノードでは左右の子ノードがないのrootだけを返す

return root

#root1かroo2のどちらか、もしくは両方がNoneの場合

else:

#root1かroot2をそのまま返す。少なくとも片方はNoneなので、どちらかの値か、Noneが返される。

return root1 or root2

解答2:

補足・参考・感想

参考

前：695. Max Area of Island

次：77. Combinations

LeetCode 解答・解説記事一覧