[LeetCode/Python] 617.두 이진 트리 병합(Merge Two Binary Trees)

 

 

 

두 이진 트리를 병합하라. 중복되는 노드는 값을 합산한다.

 

 

Example

 

 

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

 

Output: [3,4,5,5,4, null,7]

 

 

 

 

 

1. 재귀 탐색

 

 

# 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]:
        if root1 and root2:
            node = TreeNode(root1.val + root2.val)
 
            node.left = self.mergeTrees(root1.left, root2.left)
            node.right = self.mergeTrees(root1.right, root2.right)
            
            return node
        
        else:
            return root1 or root2

 

해설

 

간단하다.

 

Tree를 하나 더 만들어서

 

두 트리의 노드 value를 합하여

 

새로운 트리 노드의 값으로 넣어주면 된다.

 

만약 두 노드 중 하나가 None이라면

 

한 값만 새 트리 노드에 넣어주면 되므로

 

return root1 or root2

 

이런 식으로 처리해준다.