TreeNode 클래스와 레벨 순서 BFS
배열에서 이진 트리를 구성하고 deque로 BFS를 구현해 레벨별로 출력하며, BFS로 최대 깊이를 구합니다.
TreeNode 클래스와 레벨 순서 BFS은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
TreeNode 클래스의 기초
이진 트리는 각 노드가 최대 두 개의 자식을 가지는 계층적 자료 구조이며, 두 자식은 왼쪽과 오른쪽이라고 합니다. Python에서는 간단한 클래스로 노드를 모델링합니다. class TreeNode: def __init__(self, val=0, left=None, right=None)이 바로 그 정의입니다. 면접의 모든 트리 문제는 이 정의에서 시작하며, 거의 모든 LeetCode 트리 문제의 기본 코드에서 이를 보게 됩니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)배열로 트리 만들기
면접 문제에서는 레벨 순서 배열로 표현된 트리가 자주 주어지며, None은 누락된 노드를 나타냅니다. 인덱스 i가 주어지면 왼쪽 자식은 2i+1에, 오른쪽 자식은 2i+2에 있습니다. 이 배열을 연결된 TreeNodes로 역직렬화하는 도우미를 작성해 두면 연습 시간에 유용하고 시간을 절약할 수 있습니다.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)BFS란 무엇이며 왜 큐를 사용할까요
너비 우선 탐색(BFS)은 깊이 d에 있는 모든 노드를 방문한 후 깊이 d+1에 있는 노드를 방문합니다. 이러한 레벨별 순회는 큐(FIFO)가 제공하는 동작과 정확히 같습니다. 루트를 큐에 넣고, 노드를 하나씩 처리하면서 각 노드의 자식을 큐에 넣습니다. Python의 collections.deque는 O(1) 시간에 appendleft와 popleft를 제공하므로 일반 리스트보다 적합합니다.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4레벨 순서 BFS: 레벨별 그룹화
표준 BFS 변형에서는 각 반복을 시작할 때의 큐 크기를 기록하여 노드를 레벨별로 그룹화합니다. 정확히 그 수만큼 노드를 처리하고 값을 수집한 다음 다음 레벨로 이동합니다. 그 결과 리스트의 리스트가 만들어지며, 이는 이진 트리 레벨 순서 순회, 지그재그 순회, 오른쪽 시점 보기와 같은 문제에서 매우 자주 사용하는 면접 출력 형식입니다.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]BFS로 최대 깊이 구하기
이진 트리의 최대 깊이는 BFS 순회에서 레벨의 개수와 같습니다. 레벨 반복을 완료하는 횟수만 세면 됩니다. 이렇게 하면 시간 복잡도 O(n), 공간 복잡도 O(w)의 해법을 얻을 수 있으며, 여기서 w는 트리의 최대 너비입니다. 균형 트리에서는 w가 O(n/2)이므로 최악의 경우 공간 복잡도는 O(n)입니다.
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3이진 트리의 오른쪽 시점 보기
오른쪽 시점 보기는 트리를 오른쪽에서 바라볼 때 보이는 마지막 노드, 즉 BFS 순회에서 각 레벨의 마지막 원소를 반환합니다. 이는 레벨 순서 BFS를 직접 적용한 것으로, 각 레벨 반복에서 마지막 노드를 수집하면 됩니다. 시간 복잡도는 O(n)이고, 공간 복잡도는 큐에 필요한 O(w)입니다.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]지그재그 레벨 순회
지그재그 순회에서는 홀수 레벨의 노드를 왼쪽에서 오른쪽으로 수집하고, 짝수 레벨의 노드를 오른쪽에서 왼쪽으로 수집합니다. 가장 깔끔한 구현은 BFS 큐를 그대로 유지하면서 결과에 추가하기 전에 번갈아 레벨 목록을 뒤집는 방식입니다. 각 레벨마다 방향을 뒤집는 불리언 플래그를 사용합니다. 이렇게 하면 내부 반복문에서 양방향 덱을 다뤄야 하는 복잡성을 피할 수 있습니다.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))BFS 공간 복잡도 분석
BFS는 트리의 최대 너비를 w라고 할 때 O(w)의 공간을 사용합니다. 포화 이진 트리에 n개의 노드가 있다면 마지막 레벨에는 (n+1)/2개의 노드가 있으므로, BFS는 큐에 최대 n/2개의 노드를 동시에 보관할 수 있습니다. 따라서 너비가 넓고 균형 잡힌 트리에서는 BFS가 DFS(O(h))보다 공간 측면에서 비효율적이지만, DFS의 호출 스택 깊이가 n과 같아지는 깊고 한쪽으로 치우친 트리에서는 더 효율적입니다.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')이진 트리의 레벨별 평균
각 레벨의 평균값을 계산하는 것은 BFS를 직접 적용하는 또 다른 예입니다. 한 레벨의 모든 값을 더하고, 노드 수로 나눈 다음 결과 목록에 추가합니다. 이 문제는 레벨 반복문 안에서 산술 연산을 수행할 수 있는지 확인합니다. Python 3에서는 항상 float 나눗셈(/ 연산자)을 사용하고, 시작 부분에서 빈 트리라는 예외 상황을 처리해야 합니다.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]BFS를 통한 최소 깊이
최소 깊이는 루트에서 가장 가까운 리프 노드(자식이 없는 노드)까지의 거리입니다. BFS는 이 문제를 최적으로 해결합니다. 레벨 순회 중 처음 만나는 리프 노드는 반드시 최소 깊이에 있기 때문입니다. 리프를 만나는 즉시 현재 깊이를 반환합니다. 최악의 경우 O(n)이지만, 균형 잡힌 트리에서는 훨씬 일찍 종료되는 경우가 많습니다.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2레벨 순회 형제 노드 연결
오른쪽 다음 포인터 채우기 문제는 각 노드를 같은 레벨의 오른쪽 이웃 노드에 연결하도록 요구합니다. BFS를 사용하면 간단합니다. 각 레벨의 반복문 안에서 마지막 노드를 제외한 모든 노드에 대해 node.next = q[0]으로 설정하면 됩니다. BFS를 사용하면 해결 방법이 명확해지는 반면 DFS에서는 서브트리 사이의 포인터를 주의 깊게 추적해야 하는 전형적인 예입니다.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')빠른 확인
이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 확인해 보세요.
레슨 요약
이 레슨에서는 TreeNode 클래스 정의와 배열에서 트리를 만드는 방법, 레벨 크기 기법으로 노드를 그룹화하는 덱을 사용한 레벨 순서 BFS, 그리고 최대 깊이, 최소 깊이, 오른쪽 시점, 지그재그 순회, 레벨별 평균을 포함한 응용을 배웠습니다. 다음 레슨에서는 재귀 DFS 순회 순서를 살펴봅니다.
자주 묻는 질문
“TreeNode 클래스와 레벨 순서 BFS” 강의는 무료인가요?
네 — “TreeNode 클래스와 레벨 순서 BFS” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“TreeNode 클래스와 레벨 순서 BFS”에서 뭘 배우나요?
배열에서 이진 트리를 구성하고 deque로 BFS를 구현해 레벨별로 출력하며, BFS로 최대 깊이를 구합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“TreeNode 클래스와 레벨 순서 BFS” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TreeNode 클래스와 레벨 순서 BFS
- 중위, 전위, 후위 DFS
- 지름, 높이, 균형 이진 트리
- 경로 합과 최소 공통 조상