LeetCode 617. Merge Two Binary Trees

파이썬 알고리즘 인터뷰 문제 46번(리트코드 617번) Merge Two Binary Trees
https://leetcode.com/problems/merge-two-binary-trees/

나의 풀이

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root2:
            return root1
        if not root1:
            return root2
        result = root1

        def helper(node1, node2):
            if node1 == node2: # Include None Case
                return
            if not node2:
                return
            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            else:
                helper(node1.left, node2.left)
            if not node1.right and node2.right:
                node1.right = node2.right
            else:
                helper(node1.right, node2.right)
        
        helper(root1, root2)
        return result

다른 풀이

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[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

배운 점

• 모두 재귀 풀이이지만 다른 풀이가 더 우아하다.
• 나는 재귀함수에서 node를 return하지 않는 방식으로 풀어서 다소 복잡해졌다.
• 그렇게 선택한 이유는.
  • node = helper(root1, root2), return node 하면 .left, .right 정보가 사라지거나 꼬일 것이라 생각했다.
  • 하지만 다른 풀이처럼 node를 새로 생성하고, node.left, node.right를 재귀 함수로 정의한 다음 node를 return 하면 된다.
  • 그러니까 나는 node만 재귀 함수로 정의하고 반환할 수 있다고 생각했는데, node의 left, right를 재귀 함수로 정의하고 node를 반환하면 된다.