[알고리즘][트리] - 5. 두 이진 트리 병합

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/merge-two-binary-trees/

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

---

[재귀 탐색]

class Solution:
    def mergeTrees(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]:
        if t1 and t2: #자식노드가 모두 있을 경우
            node = TreeNode(t1.val + t2.val)
            node.left = self.mergeTrees(t1.left, t2.left)
            node.right = self.mergeTrees(t1.right, t2.right)
            return node
        else: #자식 노드가 한 쪽만 있는 경우 (둘 다 없으면 None 리턴)
            return t1 or t2

• 자식 노드가 둘 다 있을 경우라면 둘 다 모두 진행해준다.
• 둘 중 자식 노드가 없는 경우라면 한 쪽만 리턴한다.
• 모두 존재하지 않으면  None이 리턴된다.
• 후위 순위 탐색 순서로 탐색을 하고 있다.