LeetCode 풀기 - 617. Merge Two Binary Trees

617. Merge Two Binary Trees

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

Merge Two Binary Trees - LeetCode

문제)

솔루션1) - 재귀적

문제 난이도는 Easy였지만 저에게는 Medium 이상 난이도의 문제였습니다.

DFS 방식으로 계속 푸는 방법을 생각 했지만 결국에는 포기하고 Discussion을 참고 하였습니다.

 

 

노드를 생성해 나아가면서 merged tree를 만들어가는 방식입니다.

참.... 답을 풀면 정말 쉽습니다. 코드가 이렇게 간결해지는지.

 

이진 트리 문제에 대해서는 먼저 재귀적으로 풀 수 있는 방법을 먼저 고민하는 게 정답인 것 같습니다.

# 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 is None and root2 is None:
            return None
        
        v1 = root1.val if root1 else 0
        v2 = root2.val if root2 else 0
        node = TreeNode(v1+v2)
        
        node.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
        node.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)
        
        return node

솔루션2) - 재귀적

솔루션1과 문제 풀어가는 방식은 비슷합니다.

그렇지만 여기서는 별도의 트리를 구성하는 방식이 아닙니다.

기존의 첫뻔재 트리에를 머지하면서 재구성하는 방식입니다.

 

# 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 is None:
            return root2
        if root2 is None:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

 

 

함께보면 좋은 영상:

https://www.youtube.com/watch?v=QHH6rIK3dDQ 

https://www.youtube.com/watch?v=_LJO5nBKC1A