[Neetcode/Tree] Binary Tree Level Order Traversal

https://neetcode.io/problems/level-order-traversal-of-binary-tree

NeetCode

 

Level-Order Traversal이란?

Level-order traversal(레벨 순회) 는 트리(Tree) 를 탐색하는 방법 중 하나로, BFS(너비 우선 탐색, Breadth-First Search) 를 기반으로 한다.

---

트리 탐색 (Tree > Traversal)의 대표적인 방법

트리에서 노드를 방문하는 순서에 따라 탐색 방식이 여러 가지가 있다.

1. DFS (깊이 우선 탐색, Depth-First Search)
   • 루트에서 시작해서 최대한 깊이 내려간 후 백트래킹(되돌아옴).
   • 구현 방법:
     • 전위 순회 (Preorder): Root → Left → Right
     • 중위 순회 (Inorder): Left → Root → Right
     • 후위 순회 (Postorder): Left → Right → Root
   • 주로 재귀(recursion)나 스택(stack) 을 이용해서 구현.
2. BFS (너비 우선 탐색, Breadth-First Search)
   • Level-order traversal이 BFS를 이용한 대표적인 탐색 방법.
   • 같은 레벨의 노드를 먼저 방문한 후, 그다음 레벨로 내려감.
   • 큐(queue)를 이용해서 구현.

---

# 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 []
        
        result = []
        queue = deque([root])  # BFS를 위한 큐 생성
        
        while queue:
            level_size = len(queue)  # 현재 레벨의 노드 개수
            level_nodes = []  # 현재 레벨의 값들을 저장할 리스트
            
            for _ in range(level_size):
                node = queue.popleft()  # 큐에서 노드를 꺼냄
                level_nodes.append(node.val)
                
                if node.left:
                    queue.append(node.left)  # 왼쪽 자식 추가
                if node.right:
                    queue.append(node.right)  # 오른쪽 자식 추가
            
            result.append(level_nodes)  # 현재 레벨 값을 결과에 추가
        
        return result

풀이 과정

1. BFS(너비 우선 탐색) 활용
   • deque를 이용하여 큐(queue)를 생성한다.
   • 루트 노드를 큐에 넣고 탐색을 시작한다.
2. 각 레벨별로 순회
   • 현재 큐의 길이를 확인하여, 해당 레벨의 모든 노드를 처리한다.
   • queue.popleft()로 제일 앞의 노드를 꺼내서 값을 저장한 후, 왼쪽/오른쪽 자식이 있으면 큐에 추가한다.
3. 결과 저장
   • 각 레벨에서 방문한 노드들의 값을 리스트에 저장하고, 최종적으로 전체 리스트를 반환한다.

---

시간 복잡도

• O(N) (N은 노드 개수)
  • 각 노드는 한 번씩 방문되므로 선형 시간 복잡도를 가진다.

공간 복잡도

• O(N)
  • 최악의 경우, 마지막 레벨의 모든 노드를 큐에 저장해야 하므로 O(N)이 된다.