46. Merge Two Binary Trees

🎯 leetcode - 617. Merge Two Binary Trees

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 46번 문제

📌 날짜

2020.02.16

📌 시도 횟수

2 try

💡 Code

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1 and not root2:
            return None

        elif not root1:
            root1 = TreeNode(root2.val)
            
        elif not root2:
            root2 = TreeNode(None)

        else:
            root1.val = root1.val + root2.val

        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1 

💡 문제 해결 방법

- root1의 이진 트리에 root2의 이진트리 값들을 더해서 만들었다.

- 재귀를 이용해서 각각의 이진 트리를 루트부터 합쳐나가면서
현재 노드의 좌, 우 자식 노드들도 재귀 호출한다.
    > 만약 둘 다 노드가 존재하지 않으면 return None
    > 만약 root1만 존재한다면 root2 = TreeNode(None) 으로 빈 껍데기만 만들어준다.
    > 만약 root2만 존재한다면 root1 = TreeNode(root2.val)으로, 즉
    root1를 기준 트리로 삼아 구하기로 했으니까 root2의 값을 root1으로 옮겨온다.
    > 만약 둘 다 존재한다면 root1.val += root2.val을 한다.
    
- 이렇게 구한 root1, root2를 다시 각각의 좌, 우 자식 노드들에 대해 재귀 호출한다.

- 단, 이때 트리의 구조는 root1의 것이므로, root1.left, root1.right에 재귀 함수를 할당한다.
    > root1.left = self.mergeTrees(root1.left, root2.left)
    > root1.right = self.mergeTrees(root1.right, root2.right)

- 매번 실행되는 재귀 함수의 리턴 값은 기준이 되는 이진트리의 현재 노드인 root1이다.

- 위 코드는 재귀로 구현했으므로, 리턴 순서는 "리프에서 루트까지"인 역방향이다.
DFS로 가장 나중에 탐색한 노드부터 차례대로 값이 확실히 정해진다.

- 따라서 return root1을 했을 때, 최종적으로 리턴되는 노드는
최종적으로 병합이 모두 끝난 이진트리의 루트 노드인 root1이다.

💡 새롭게 알게 된 점

🤔 root2 = TreeNode(None) 이렇게 구현한 이유?

• 사실 이렇게 구현해도 된다

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1 and not root2:
            return None

        elif not root1:
            root1 = TreeNode(root2.val)
            root1.left = self.mergeTrees(root1.left, root2.left)
            root1.right = self.mergeTrees(root1.right, root2.right)

        elif not root2:
            root1.left = self.mergeTrees(root1.left, None)
            root1.right = self.mergeTrees(root1.right, None)

        else:
            root1.val = root1.val + root2.val
            root1.left = self.mergeTrees(root1.left, root2.left)
            root1.right = self.mergeTrees(root1.right, root2.right)

        return root1 

• 근데 코드 중복이 좀 많아서 지저분해보인다.
• 그래서 elif not root2: root2 = TreeNode(None)처럼 root2에 틀만 만들어 주면
  root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.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 # 둘 중 존재하는 것을 리턴
        
        # ✔ 양쪽 모두 존재하지 않으면?
        # 파이썬은 아무것도 리턴하지 않으면 자연스럽게 None을 할당한다.
        # 따라서 따로 조건문을 추가하지 않아도 return None이 실행된다.

💡 문제 해결 방법

- 이 풀이에서는 새로운 TreeNode를 하나 추가했다.
- 이 node라는 새로운 TreeNode의 노드를 재귀 호출로 점점 확장시켜나가는 방식이다.
- 만약 한쪽 노드만 존재하거나 양쪽 다 존재하지 않으면 리턴하여 재귀를 진행하지 않는다.
- 만약 양쪽 노드 모두 존재하지 않으면 자동적으로 None이 리턴되며
확장시킨 새로운 TreeNode에 가장 나중에 DFS로 탐색한 노드부터 값을 할당한다.

💡 새롭게 알게 된 점

✔ return root1 or root2
- 둘 중 존재하는 노드만 리턴하게 되는 코드이다.

Q. 왜 return None에 대한 코드가 없을까?
- 파이썬은 아무것도 리턴하지 않으면 자연스럽게 None을 할당한다.
- 따라서 따로 조건문을 추가하지 않아도 return None이 실행된다.