[Leetcode] 102. Binary Tree Level Order Traversal_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '102. Binary Tree Level Order Traversal'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Binary Tree Level Order Traversal' 알고리즘 문제

 

STEP 2. 'Binary Tree Level Order Traversal' 코드(code)

 

STEP 3. 'Binary Tree Level Order Traversal' 해설

 

STEP 4. 'Binary Tree Level Order Traversal' solution

 

반응형

 

STEP 1. 'Binary Tree Level Order Traversal' 알고리즘 문제

 

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

이진트리의 루트가 주어졌을 때, 노드의 값을 왼쪽에서 오른쪽으로, 레벨별로 순서대로 반환하세요.

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

---

STEP 2. 'Binary Tree Level Order Traversal' 코드(code)

 

■ Runtime: 0ms Beats 100.00%
■ Memory: 18.41MB Beats 60.93%

 

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        answer_lst = []
        que = deque([root])

        while que:         
            temp_lst = []

            for _ in range(len(que)) :
                node = que.popleft()
                temp_lst.append(node.val)
                if node.left: que.append(node.left)
                if node.right: que.append(node.right)

            answer_lst.append(temp_lst)
        
        return answer_lst

---

STEP 3. 'Binary Tree Level Order Traversal' 해설

 

큐(queue)를 이용해 각 레벨별 노드를 탐색하며, 각 노드의 값을 temp_lst에 저장합니다. 현재 레벨의 모든 노드를 처리한 후 temp_lst를 answer_lst에 추가하고, 모든 레벨을 순회한 뒤 최종적으로 answer_lst를 반환하도록 구성하였습니다.

 

 

STEP 4. 'Binary Tree Level Order Traversal' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 0ms Beats 100.00%
■ Memory: 18.68MB Beats 18.13%

 

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        if not root:
            return res
        
        q = collections.deque()
        q.append(root)
    
        while q:
            same_level = []

            for _ in range(len(q)):
                node = q.popleft()
                same_level.append(node.val)

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            res.append(same_level)
        
        return res

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '102. Binary Tree Level Order Traversal'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.