leetCode - Merge Two Binary Trees

leetcode.com/problems/merge-two-binary-trees/

 

풀이 1)

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        
        if not root1:
            return root2
        if not root2:
            return root1
        
        def dfs(node1, node2):
            node1.val += node2.val
            if node1.left and not node2.left:
                node2.left = TreeNode()
            if node2.left and not node1.left:
                node1.left = TreeNode()
            if node1.right and not node2.right:
                node2.right = TreeNode()
            if node2.right and not node1.right:
                node1.right = TreeNode()
                
            if node1.left:
                dfs(node1.left, node2.left)
            if node1.right:
                dfs(node1.right, node2.right)

        dfs(root1, root2)
        
        return root1

두 트리를 모두 dfs로 들어가면서 양쪽 중 한 쪽의 왼쪽/오른쪽 노드가 없는 부분을 0으로 만들어서 넣어준다. 

node1.left 는 node1이 None이면 에러가 나므로 예외 케이스 1) root1 == None, 2) root2 == None 인 경우를 함수 맨 앞에서 처리한다.

 

매우 난해한 풀이이다..

 

 

 

풀이 2)

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

merge sort 처럼 그냥 '무책임하게 재귀로 떠넘기기' 하면 된다