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.

입출력 예시

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)
        

해설

입력을 예로 들어서 설명한다.

1. 두 트리 모두 루트가 있으므로 root 1 and root2에 의해
   new_node=TreeNode(3)이 생성된다.
   

2. 왼쪽으로 가본다. 부모 노드(값 3)는 그 결괏값을 기다린다.
   왼쪽으로 간 분기에서는 val = 1 + 3 = 4인 노드가 생성된다.
   

3. 왼쪽으로 가본다. 부모 노드(값 4)는 그 결괏값을 기다린다.
   왼쪽으로 간 분기에선 root2가 None이다. 기저 조건에 의해 root1을 리턴한다.
   

4.root1의 노드 (값 5)는 리턴되어 기다리고 있던 부모노드의 왼쪽에 부착된다.
new_node.left=self.recursion(root1.left,root2.left)

5. 3.의 분기에서 이번엔 오른쪽에 가본다. 부모노드는 그 결괏값을 기다린다. 오른쪽으로 간 분기에선 root1이 None이다. 기저조건에 의해 root2를 리턴한다.
   

6. root2의 노드 (값 4)는 리턴되어 기다리고 있던 부모 노드의 오른쪽에 부착된다.
   new_node.right=self.recursion(root1.right,root2.right)
   

7. 3.의 분기가 모두 끝났으므로 노드 (값 4)를 리턴한다. 기다리고 있던 부모 노드 (루트노드. 값 3)은 해당 노드를 왼쪽에 부착한다.
   

(오른쪽도 동일한 처리이므로 이하 생략)

익숙해질 때까지 풀어봐야 할 듯...