617.結合バイナリツリー

問題の説明

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.

I/O例

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

こうそくじょうけん

The number of nodes in both trees is in the range [0, 2000].
-104 <= Node.val <= 104

完全なコード

# 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 recursion(self,root1,root2):            
        if root1 and root2:
            new_node=TreeNode(root1.val+root2.val)
            
            new_node.left=self.recursion(root1.left,root2.left)
            new_node.right=self.recursion(root1.right,root2.right)
            
            return new_node
        elif root1:
            return root1
        elif root2:
            return root2
        else:
            return None

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

解説

入力を例に説明します.

どちらの木にも根があるので、root 1 and root2new_node=TreeNode(3)を生成します.

左へ行く.親ノード(値3)は、リンゴの値を結ぶのを待っています.
左のブランチでval=1+3=4のノードが作成されます.

左へ行く.親ノード(値4)は、欠落した値を待機します.
左分岐ではroot 2はNoneであった.ベース条件に基づいてroot 1を返します.

4.root 1のノード(値5)は、待機中の親ノードの左側に戻ります.new_node.left=self.recursion(root1.left,root2.left)

第3四半期には、今度は右側に行きます.親ノードは、リンゴの値を結ぶのを待っています.右側のブランチではroot 1はNoneです.基本条件に基づいてroot 2を返します.

root 2のノード(値4)は、返されて待機している親ノードの右側にアタッチされます.new_node.right=self.recursion(root1.right,root2.right)

3.のブランチはすべて終了し、ノード(値4)に戻ります.待機している親ノード(ルートノード.値3)は、そのノードを左側にアタッチします.

(右側も同様の処理で、以下は省略)
慣れるまで解いてみるべきだと思いますが...