[파이썬 알고리즘 인터뷰][트리] 두 이진 트리 병합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

로그 재정렬 기준

1.  

 

책에서 구현된 코드

class Solution:
    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

 

기억해야할 기법

• return t1 or t2
  
  • 둘 중 하나가 존재하면, 존재하는 객체 리턴
  • 둘 다 존재하지 않는다면, None 리턴
• 재귀를 이용하여 리턴되는 노드가 left / right로 오는 형태

 

내가 구현한 코드

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        def dfs(res: TreeNode, node1: TreeNode, node2: TreeNode):
            val1 = val2 = 0
            node1_l = node1_r = node2_l = node2_r = None
            # 현재 노드의 값 계산
            if node1:
                val1 = node1.val
                node1_l = node1.left
                node1_r = node1.right
            if node2:
                val2 = node2.val
                node2_l = node2.left
                node2_r = node2.right
            res.val = val1 + val2

            # left / right 재귀
            if node1_l or node2_l:
                res.left = res_l = TreeNode()
                dfs(res_l, node1_l, node2_l)
            if node1_r or node2_r:
                res.right = res_r = TreeNode()
                dfs(res_r, node1_r, node2_r)

        if root1 is None and root2 is None:
            return None
        result = TreeNode()
        dfs(result, root1, root2)
        return result

• 속도는 비슷하지만, 작성한 코드의 차이가 어마어마하다
• 리턴 방식이 신기하다 (or를 사용했는데 boolean이 아니다)
• 꼭 기억해야할 설계다