[1스4코2파] #132. LeetCode Algorithm Day 8 (617. Merge Two Binary Trees, 116. Populating Next Right Pointers in Each Node)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (132일차)
[4코1파] 2023.01.13~ (123일차)
[1스4코1파] 2023.04.12~ (34일차)
[1스4코2파] 2023.05.03 ~ (13일차)

Today :

2023.05.15 [132일차]

LeetCode Algorithm Day 7
617. Merge Two Binary Trees
https://leetcode.com/problems/merge-two-binary-trees/?envType=study-plan&id=algorithm-i

567. Max Area of Island

• https://leetcode.com/problems/max-area-of-island/?envType=study-plan&id=algorithm-i

문제 1

[617] Merge Two Binary Trees
https://leetcode.com/problems/merge-two-binary-trees/?envType=study-plan&id=algorithm-i

내 코드

# 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라는 자료형을 가진 트리의 root가 들어오고, 해당 트리는 완벽한 이진트리이다.
level이 끝날 때 마다 해당 노드의 next 값에 '#'를 부여 한다.
?

증빙

---

문제 2

[116] Populating Next Right Pointers in Each Node
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/?envType=study-plan&id=algorithm-i

내 코드

from collections import deque

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        
        queue = deque()
        dummy = Node()
        dummy2 = dummy
        queue.append(root)
        
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                
                dummy.next = Node(node.val)
                dummy = dummy.next
                
            if len(queue)!=0:
                dummy.next = Node('#') 
                dummy = dummy.next
                
        return dummy2.next

문제 풀이 방법

풀이방법? 구글에 LeetCode 116 python ㅗㅗ

증빙

여담

이거 진짜 뭔데...