[정글 코어타임] - [리트코드]102. Binary Tree Level Order Traversal

LeetCode · Tree · BFS · Medium

이진 트리를 층별(level by level)로 탐색하면서 각 레벨의 값을 따로 모아 반환하는 대표적인 BFS 문제

문제 링크 바로가기

문제 한눈에 보기

입력	이진 트리의 루트 노드 root
출력	[[레벨1], [레벨2], ...] 형태의 2차원 리스트
핵심 조건	왼쪽에서 오른쪽 순서로, 위에서 아래 레벨 순서대로 방문
대표 풀이	BFS(너비 우선 탐색) + 큐 + 현재 레벨 크기 저장

문제 설명 요약: 루트에서 시작해서 같은 깊이의 노드들을 한 묶음으로 모은 뒤, 그 다음 깊이로 내려가며 값을 저장하면 된다.

핵심 1

이 문제는 BFS의 정석 패턴이다. 큐를 이용하면 현재 층의 노드들을 순서대로 처리할 수 있다.

핵심 2

레벨 단위로 끊어 담기 위해, while이 한 번 돌 때마다 시작 시점의 큐 길이를 저장해야 한다.

핵심 3

현재 레벨을 처리하면서 자식 노드를 큐 뒤에 넣으면, 그 자식들은 자동으로 다음 레벨이 된다.

왜 BFS로 풀까?

DFS는 한쪽으로 깊게 들어가는 탐색이라서 “층별로 잘라서 보기”에는 바로 맞지 않는다. 반면 BFS는 큐를 사용해 가까운 노드부터 차례대로 방문하므로, 자연스럽게 루트 → 2층 → 3층 순서로 진행된다.

이 문제의 핵심은 “노드를 방문하는 것” 자체보다, 같은 깊이에 있는 노드들을 하나의 리스트로 모으는 것이다.

예제 시각화

입력 예시: root = [3,9,20,null,null,15,7]

3 / \ 9 20 / \ 15 7

반복	시작 시 큐	level_size	이번 레벨 결과	끝난 뒤 큐
1번째 while	[3]	1	[3]	[9, 20]
2번째 while	[9, 20]	2	[9, 20]	[15, 7]
3번째 while	[15, 7]	2	[15, 7]	[]

최종 결과는 [[3], [9, 20], [15, 7]] 이다.

왜 level_size = len(queue) 가 중요한가?

이 줄이 없으면 현재 레벨과 다음 레벨이 섞이기 쉽다. 큐에는 현재 레벨 노드들이 먼저 들어 있고, 그 노드들을 처리하는 도중에 다음 레벨 자식들이 뒤에 추가된다.

따라서 while 시작 시점의 큐 길이를 미리 저장해 두고, 그 개수만큼만 꺼내야 “이번 층”만 정확히 처리할 수 있다.

level_size = len(queue) for _ in range(level_size): node = queue.popleft() ... if node.left: queue.append(node.left) if node.right: queue.append(node.right)

즉, 위 코드는 “이번 층에 있던 노드만 처리하고, 새로 들어온 자식들은 다음 while에서 처리하겠다”라는 의미다.

최종 코드

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
        
        return result

한 줄씩 자세히 설명

줄	코드	설명
1	from collections import deque	BFS에서는 큐 자료구조가 필요하다. 파이썬에서는 deque가 앞에서 꺼내고 뒤에 넣기 편해서 큐 구현에 자주 사용된다.
3	class Solution:	LeetCode에서 요구하는 클래스 형식이다.
4	def levelOrder(...)	트리의 레벨 순회 결과를 반환하는 함수다. 반환형은 2차원 리스트다.
5-6	if root is None: return []	트리가 비어 있으면 순회할 노드가 없으므로 빈 리스트를 바로 반환한다.
8	result = []	각 레벨의 결과를 차곡차곡 담을 최종 리스트다.
9	queue = deque([root])	탐색의 시작점은 루트이므로 큐에 루트를 넣고 시작한다.
11	while queue:	큐가 빌 때까지 반복한다. 큐가 비면 모든 노드를 처리한 것이다.
12	level_size = len(queue)	현재 while 시작 시점의 큐 길이를 저장한다. 바로 이 값이 이번 레벨의 노드 개수다.
13	level = []	이번 레벨의 노드 값만 따로 담기 위한 임시 리스트다.
15	for _ in range(level_size):	현재 레벨의 노드 수만큼만 반복한다. 새로 추가되는 자식 노드는 이번 레벨에 포함되지 않는다.
16	node = queue.popleft()	큐의 맨 앞 노드를 꺼낸다. BFS이므로 먼저 들어온 노드부터 처리한다.
17	level.append(node.val)	현재 노드의 값을 이번 레벨 리스트에 저장한다.
19-20	if node.left: queue.append(node.left)	왼쪽 자식이 존재하면 큐 뒤에 넣는다. 이 자식은 다음 레벨에서 처리된다.
21-22	if node.right: queue.append(node.right)	오른쪽 자식도 존재하면 큐 뒤에 넣는다.
24	result.append(level)	이번 레벨 처리가 모두 끝났으므로 결과 리스트에 추가한다.
26	return result	모든 레벨 순회를 마친 뒤 최종 결과를 반환한다.

동작 흐름 요약

1. 루트를 큐에 넣기

2. while queue 반복

3. 현재 큐 길이를 저장

4. 그 개수만큼만 꺼내기

5. 값 저장 + 자식 큐에 넣기

6. level을 result에 추가

시간복잡도

모든 노드를 정확히 한 번씩 꺼내고 처리하므로 O(n)

공간복잡도

큐에 한 레벨의 노드가 많이 들어갈 수 있으므로 최악의 경우 O(n)

자주 하는 실수

실수	왜 문제인지
레벨 구분 없이 큐가 빌 때까지 한 번에 다 꺼냄	모든 노드가 한 리스트에 섞여 들어가서 층별 결과가 안 나온다.
level_size를 매 반복마다 다시 계산함	자식이 들어오며 큐 길이가 변해 현재 레벨과 다음 레벨이 섞일 수 있다.
빈 트리 예외 처리 없음	root가 None일 때 오류가 나거나 잘못된 결과가 나올 수 있다.
DFS로 풀면서 레벨 관리 없이 값만 저장함	DFS도 가능은 하지만 이 문제의 의도와는 다르게 깊이 정보 추가 관리가 필요해져 더 번거롭다.

핵심 요약

• 이 문제는 레벨 순서 탐색 = BFS 라고 바로 연결되는 대표 문제다.
• 큐에는 현재 레벨 노드들이 들어 있고, 처리 도중 추가되는 자식들은 다음 레벨이 된다.
• level_size = len(queue) 로 현재 층의 노드 수를 먼저 고정하는 것이 가장 중요하다.
• 각 while마다 하나의 level 리스트를 만들고, 끝나면 result에 추가하면 된다.

한 문장 정리

루트에서 시작해 큐로 한 층씩 처리하고, 각 while 반복마다 현재 큐 길이만큼만 꺼내면 레벨 순회 결과를 정확하게 만들 수 있다.

출처: LeetCode 102. Binary Tree Level Order Traversal