46. Merge Two Binary Trees

리트코드

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

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: TreeNode, root2: TreeNode) -> 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

• 각각 이진트리의 루트부터 시작해 합쳐 나가면서 좌, 우 자식 노드 또한 병합될 수 있도록 각 트리 자식 노드를 재귀 호출한다.

  • 만약 어느 한쪽에 노드가 존재하지 않는다면 not (root1 and root2) 존재하는 노드만 리턴하고 더 이상 재귀 호출을 진행하지 않는다.

  • 양쪽 노드가 모두 존재하지 않는다면 None이 리턴될 것이다.

<두 트리가 합쳐지면서 리턴되는 순서>

• 이 그림은 양쪽 노드가 모두 존재하지 않아 None이 리턴되는 경우를 비롯한 모든 탐색의 경우를 볼 수 있다.

• 탐색 순서는 파란 글씨로 숫자를 붙였다.

  • 여기서 순서는 백트래킹되는 순서를 기준으로 한다.

• 가장 말단인 1번부터 리턴 값을 차례대로 받아오며, 9)번에서 모든 리턴이 마무리되고 병합된 최종 결과가 남게 되면서 탐색이 종료된다.

  • 리턴 순서만 놓고 본다면 탐색 순서는 후위 순회(Post-Order)임을 확인할 수 있다.