[정글 코어타임] - [리트코드] 637. Average of Levels in Binary Tree

LeetCode · Tree · BFS · Easy

이진 트리의 각 레벨을 순회하면서 레벨별 평균값을 구하는 대표적인 BFS 문제

문제 링크 바로가기

문제 한눈에 보기

문제	각 레벨에 있는 노드 값들의 평균을 배열 형태로 반환하기
출력 형태	[3.0, 14.5, 11.0] 같은 레벨별 평균 리스트
핵심 아이디어	현재 레벨 노드들을 한 번에 꺼내서 합계와 개수를 구한 뒤 평균 계산
대표 풀이	BFS(레벨 순회) + 큐 + level_size 사용

핵심 1

이 문제는 레벨 순회(BFS) 로 푸는 것이 가장 자연스럽다.

핵심 2

각 레벨마다 합계와 노드 개수를 구해서 합 / 개수 를 저장하면 된다.

핵심 3

level_size = len(queue) 가 현재 레벨을 구분하는 가장 중요한 장치다.

왜 BFS가 가장 자연스러울까?

평균은 레벨별로 구해야 하므로, 한 층씩 나눠서 처리하는 BFS가 딱 맞는다. 현재 레벨의 노드들만 꺼내서 합계를 구하고, 그 다음 자식들은 자연스럽게 다음 레벨이 된다.

이 문제의 핵심은 현재 레벨만 정확히 끊어서 처리하는 것이다. 그래서 큐의 길이를 미리 저장하는 방식이 중요하다.

정답 코드

from collections import deque

class Solution(object):
    def averageOfLevels(self, root):
        queue = deque([root])
        result = []

        while queue:
            level_size = len(queue)
            level_sum = 0

            for i in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(float(level_sum) / level_size)

        return result

핵심 아이디어

큐 안에는 항상 현재 레벨의 노드들이 먼저 들어 있다.

예를 들어 처음에는 queue = [root] 이므로 레벨 0 노드 1개만 들어 있다.

그리고 level_size = len(queue) 를 하면, 이번 레벨에서 처리해야 할 노드 개수를 알 수 있다.

그 개수만큼만 꺼내면서 자식들을 다시 큐에 넣으면, 반복문이 끝났을 때 큐에는 자동으로 다음 레벨 노드들만 남게 된다.

한 줄씩 설명

순서	코드	설명
1	queue = deque([root])	BFS용 큐를 만든다. 처음에는 루트 노드 하나만 넣는다.
2	result = []	각 레벨의 평균값을 저장할 리스트다.
3	while queue:	큐가 빌 때까지 반복한다. 즉, 모든 레벨을 다 처리할 때까지 돈다.
4	level_size = len(queue)	현재 큐에 들어 있는 노드 개수를 저장한다. 이 값이 바로 현재 레벨의 노드 수다.
5	level_sum = 0	현재 레벨 값들의 합을 저장할 변수다.
6	for i in range(level_size):	현재 레벨의 노드 수만큼만 꺼낸다. 이게 레벨 구분의 핵심이다.
7	node = queue.popleft()	큐 맨 앞의 노드를 꺼낸다.
8	level_sum += node.val	현재 노드의 값을 레벨 합계에 더한다.
9	if node.left: ... if node.right: ...	자식 노드가 있으면 큐에 넣는다. 지금 넣는 자식들은 다음 레벨 노드들이다.
10	result.append(float(level_sum) / level_size)	현재 레벨 평균을 구해서 결과에 넣는다. 반환형이 float 리스트이므로 실수 형태로 저장한다.
11	return result	모든 레벨 평균이 들어 있는 리스트를 반환한다.

예시로 흐름 보기

입력:

root = [3,9,20,null,null,15,7]

3 / \ 9 20 / \ 15 7

레벨	처리 노드	합계	평균	처리 후 큐
0	3	3	3.0	[9, 20]
1	9, 20	29	14.5	[15, 7]
2	15, 7	22	11.0	[]

최종 결과는 [3.0, 14.5, 11.0] 이다.

헷갈릴 수 있는 포인트

질문	설명
입력을 한 번에 주는데 레벨은 어떻게 구분하나?	LeetCode는 이미 배열 입력으로 트리를 만들어서 root 로 전달한다. 우리는 배열을 직접 다루는 것이 아니라 연결된 트리 구조를 탐색한다.
레벨 구분 기준은 무엇인가?	레벨 구분은 배열이 아니라 현재 큐 길이로 한다. 즉, level_size = len(queue) 순간 큐 안의 노드들이 현재 레벨 전체다.
DFS로도 가능한가?	가능은 하지만 깊이별 합계와 개수를 따로 저장해야 해서 BFS보다 덜 직관적이다.
왜 float로 나누나?	문제가 레벨별 평균을 실수 배열로 반환하라고 했기 때문이다.

시간복잡도

모든 노드를 한 번씩 방문하므로 O(n)

공간복잡도

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

한 줄 요약

이 문제는 큐로 레벨 순회하고, 현재 큐 길이만큼만 꺼내서, 그 레벨의 합을 구한 뒤 평균을 넣으면 되는 BFS 문제다.

핵심 정리

레벨 평균 문제는 결국 "현재 레벨 노드들을 정확히 끊어 처리할 수 있느냐"가 핵심이고, 그 역할을 level_size = len(queue) 가 담당한다.

출처: LeetCode 637. Average of Levels in Binary Tree