[알고리즘] Leetcode #617 두 이진 트리 병합 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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.

 

입출력 예

Example 1:

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

Example 2:

Input: root1 = [1], root2 = [1,2] Output: [2,2]

 

Constraints

• The number of nodes in both trees is in the range [0, 2000].
• -104 <= Node.val <= 104

 

Code

def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> 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:
        return t1 or t2

이 문제는 트리 두 개를 병합하는 것이 목표인데, 같은 자리에 두 트리 모두 값이 있다면 더한 값을 노드값으로 삼고, 둘 중 하나의 트리만 값을 가진다면 원래 노드 그대로 병합하는 방식이다. 이를 위해 mergeTrees함수로 재귀 구조를 만들었다. if문을 사용해 트리가 2개 모두 존재하는 경우와 아닌 경우를 나누었다. 이때, 계산은 가장 아래 리프노드부터 상향식 처리되며, 재귀 순서에 따라 왼쪽 자식노드부터 처리된 후 오른쪽 자식노드로 넘어간다. 또한, t1, t2 트리노드 모두 None일 때는 None을 반환한다.