617. Merge Two Binary Trees

Merge Two Binary Trees - LeetCode

1. 나의 Trash Garbage 코드

class Solution:
    def search(self, p1, p2):
        p1.val += (p2.val if p2 else 0)
        if p1.left:
            if p2:
                self.search(p1.left, p2.left)
            else:
                self.search(p1.left, TreeNode(0, None, None))

        else:
            if p2 and p2.left:
                p1.left = p2.left
                self.search(p1.left, TreeNode(0, None, None))
        if p1.right:
            if p2:
                self.search(p1.right, p2.right)
            else:
                self.search(p1.right, TreeNode(0, None, None))
        else:
            if p2 and p2.right:
                p1.right = p2.right
                self.search(p1.right, TreeNode(0, None, None))

    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
        self.search(root1, root2)
        return root1

 

2. 섹시한 코드

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1 and not root2:
            return None
        new_root = TreeNode((root1.val if root1 else 0) + (root2.val if root2 else 0))
        new_root.left = self.mergeTrees(root1 and root1.left, root2 and root2.left)
        new_root.right = self.mergeTrees(root1 and root1.right, root2 and root2.right)
        return new_root

 

내 코드는 엄밀히 말하면 새 트리를 만들지 않고, 기존 트리 중 하나에 값을 업데이트한다. 두 번째 코드는 새 트리를 만드는 코드다.

문제에선 두 트리를 합쳐서 새로운 트리를 만들라고 했으니 2번이 의도도, 코드도 더 적합하다고 볼 수 있다.

 

3. 더 직관적이라고 생각이 드는 코드

class Solution:
    def mergeTrees(self, t1, t2):
            if t1 and t2:
                root = TreeNode(t1.val + t2.val)
                root.left = self.mergeTrees(t1.left, t2.left)
                root.right = self.mergeTrees(t1.right, t2.right)
                return root
            else:
                return t1 or t2

 

사실 2번 코드와 골자는 같다. 그런데 훨씬 더 이해하기 쉽고 return t1 or t2 구문을 통해서 t1과 t2중 하나만 있다면 그 노드를, 둘 다 없다면 None을 반환해서 재귀 조건을 설정했다.

 

변명하자면 나는 새로운 트리를 만들어서 하는 것보다 기존 트리를 이용해서 하는 게 메모리를 사용하지 않아서 더 효율적이라고 생각했고, 그래서 기존 트리에 값을 반영하는 로직으로 코드를 작성했지만...