[Leetcode/Tree] 617. Merge Two Binary Trees

# 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 not root1: # root1이 None이면 root2 반환
            return root2
        if not root2: # root2가 None이면 root1 반환
            return root1
        
        # 두 노드 값 더하기
        merged = TreeNode(root1.val + root2.val)

        # 왼쪽, 오른쪽 자식 노드 재귀적으로 합치기
        merged.left = self.mergeTrees(root1.left, root2.left)
        merged.right = self.mergeTrees(root1.right, root2.right)

        return merged

풀이 방법 (DFS)

1. 베이스 케이스:
   • root1과 root2가 둘 다 None이면 None을 반환한다.
   • 둘 중 하나가 None이면 None이 아닌 노드를 반환한다.
2. 현재 노드 처리:
   • root1과 root2가 모두 존재하면 두 노드의 값을 더한 새로운 노드를 만든다.
3. 좌우 서브트리 재귀 호출:
   • left와 right 서브트리에 대해 같은 방식으로 재귀 호출한다.
4. 병합된 새로운 트리를 반환한다.