[LEET CODE] 617. Merge Two Binary Trees

# Problem

You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree. Return the merged tree. Note: The merging process must start from the root nodes of both trees.     Constraints: The number of nodes in both trees is in the range [0, 2000]. -104 <= Node.val <= 104

 

# My Answer

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        def merge(r1,r2):
            if r1 and r2:
                r1.val = r1.val + r2.val
            elif r2 and not r1:
                r1 = r2
            else:
                return r1
                
            if r1.left and r2.left:
                r1.left = merge(r1.left,r2.left)
            elif r2.left and not r1.left:
                r1.left = r2.left
            if r1.right and r2.right:
                r1.right = merge(r1.right,r2.right)
            elif not r1.right and r2.right:
                r1.right = r2.right
            return r1
        return merge(root1,root2)

 

# Solution 1 - 재귀 탐색

import collections

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

양쪽 모두 존재하는 경우 재귀 호출

한쪽만 존재하는 경우 존재하는 노드만 리턴 ( 양쪽 모두 존재하지 않으면 None 리턴 )