[리트코드/leetcode/python] 102. Binary Tree Level Order Traversal

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이 문제는 지난 PreOrder 문제에 이어 Level Order Traversal 문제입니다.

Level Order는 말그대로 레벨 순으로 순회를 하는 것인데, 트리에서는 보통 root 노드부터 레벨 1로 시작되고 아래로 내려오면서 level이 증가합니다.

 

해당 문제에서는 레벨별로 노드를 묶는 것이 관건인데요, 코드를 살펴보면서 설명드리겠습니다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        
        if not root:
            return None
        
        queue = deque([root])
        answer = []

        while queue:
            level = []
            length = len(queue)
            for _ in range(length):
                now = queue.popleft()
                level.append(now.val)
                if now.left:
                    queue.append(now.left)
                if now.right:
                    queue.append(now.right)
            answer.append(level)
        
        return answer

Level Order Traversal은 레벨별로 탐색한다는 점에서 BFS 개념으로 봐도 되는데요, 저는 큐와 스택의 성질을 모두 가지고 있는 덱을 사용했습니다.

deque의 장점은 자유자재로 양끝에서 원소를 넣다 뺐다 할 수 있고, 삽입 삭제 연산에서 O(1)의 복잡도를 가짐과 동시에, 스택/큐와 달리 index를 통해 요소들에 탐색이 가능하므로 이 역시 O(1)의 시간복잡도를 가집니다.

 

 

트리노드 형태인 root를 출력해보면, 아래와 같은 형태를 가지므로, 해당 형태에 유의하면서 코드를 살펴봅시다.

맨 처음에는 root 트리노드를 리스트 형태로 deque에 넣어주고, 이 덱이 빌 때 까지 while문을 도는데요, 이 때, level 별 노드를 구분시켜줄 수 있는 level 이라는 빈 리스트도 생성해줍니다.

 

반복은 덱의 길이만큼 해주되, 현재 바라보고 있는 노드를 now로 설정해주고, 그 now노드의 value를 level 리스트에 넣어줌으로써 해당 레벨에 들어가는 노드가 무엇인지 확정합니다.

 

만약 현재 바라보고 있는 노드의 왼쪽트리가 존재한다면, 덱에 왼쪽트리를 넣어주고,

현재 바라보고 있는 노도의 오른쪽 트리가 존재한다면, 덱에 오른쪽트리를 넣어줍니다.

 

덱의 길이만큼 돌았다면 해당 레벨을 다 살펴본 것이므로, 최종 답 리스트에 레벨별 리스트를 추가해줍니다.

 

이 작업을 전체 덱이 빌 때까지 해주면 됩니다.

 

이상으로 Binary Tree Level Order Traversal 문제를 정리해봤습니다.