637. Average of Levels in Binary Tree

난이도: 쉬움 (Easy)

링크: LeetCode 637

풀이 날짜: 2025/10/09(품)

 

---

1. 문제 이해

 

주어진 이진 트리에서 각 레벨(level)별 노드 값의 평균을 구해야 한다.

즉, 루트부터 시작해 같은 깊이의 노드들을 모아 평균을 내고, 이를 배열로 반환한다.

---

2. 접근 방식 및 자료 구조

이 문제는 두 가지 방식으로 접근할 수 있는데, 나의 경우 깊이 우선 탐색 방식으로 풀었다.

 

DFS 방식 (깊이 우선 탐색)

• 각 노드를 방문하면서 depth를 추적한다.
• depth별로 값을 모으기 위해 result를 객체 형태로 관리한다.
• 예: { 0: [3], 1: [9, 20], 2: [15, 7] }
• 모든 노드를 탐색한 후, 각 배열의 평균을 계산한다.

BFS 방식 (너비 우선 탐색)

• 큐(queue)를 사용해 레벨 단위로 순회한다.
• 한 레벨의 노드들을 모두 큐에서 꺼내고, 그 값들의 평균을 구한다.
• 이 과정을 트리의 모든 레벨이 끝날 때까지 반복한다.

---

 

3. 시간 및 공간 복잡도

• 시간 복잡도: O(n) — 모든 노드를 한 번씩 방문
• 공간 복잡도:
  • DFS: O(h) — 재귀 호출 스택 (h는 트리의 높이)
  • BFS: O(w) — 큐에 저장되는 최대 노드 수 (w는 트리의 최대 너비)

---

4. DFS 풀이

var averageOfLevels = function(root) {
    let result = []; // [[2],[1,2],[2,3,4,5]]

    function dfs(node, depth) {
      if(!node) return;

      if(!result[depth]) {
        result[depth] = []
      }

      result[depth].push(node.val);

      dfs(node.left, depth + 1);
      dfs(node.right, depth + 1);
    }

    dfs(root, 0);

    return result.map(v => v.reduce((a,c) => a+c, 0) / v.length);
};

 

핵심 포인트

• depth를 이용해 각 레벨별 데이터를 구분하는데 배열에서 인덱스에 해당한다.
• 모든 노드 탐색 후 reduce로 평균 계산
• 간결하지만, 재귀 스택이 깊은 트리에서는 메모리 사용이 많아질 수 있다.

---

5. BFS 풀이

var averageOfLevels = function(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const len = queue.length;
        let sum = 0;

        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            sum += node.val;

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(sum / len);
    }

    return result;
};

 

핵심 포인트

• 큐(queue)를 이용해 레벨 단위로 탐색
• 각 레벨의 노드를 한 번에 순회하면서 합계를 구하고 평균으로 변환
• DFS보다 직관적이며, 트리의 구조를 한 눈에 보기 쉬움

---

6. 정리

	DFS	BFS
접근 방향	깊이 우선 (재귀)	너비 우선 (큐)
자료 구조	객체(Map)로 depth별 저장	큐(queue)
장점	코드가 간결하고 직관적	레벨 단위 처리가 자연스럽다
단점	깊은 트리에서는 재귀 깊이 문제 발생 가능	큐 메모리 부담이 생길 수 있음

 

결론:

두 방법 모두 O(n)으로 효율적이지만,

• 트리 깊이가 얕거나 재귀에 익숙하다면 DFS,
• 레벨별 평균을 직관적으로 구하고 싶다면 BFS가 적합하다.