102. Binary Tree Level Order Traversal

• 난이도: 중간(Medium)
• 링크: LeetCode 102
• 풀이날짜: 2025/10/10

---

1. 문제 이해

 

이 문제는 이진 트리의 각 레벨별 노드 값을 배열 형태로 반환하는 문제로,

루트부터 시작해서 같은 깊이에 있는 노드들을 왼쪽에서 오른쪽 순서로 묶어서 리턴해야 한다.

---

2. 접근 방식 및 자료 구조

레벨 단위로 탐색하기 위해 BFS(너비 우선 탐색) 을 사용한다.

BFS는 큐(Queue)를 활용해 트리를 한 레벨씩 순서대로 순회하기에 적합하므로,

• 큐에 노드를 넣고,
• 같은 레벨의 노드들을 for문으로 순회하면서 group 배열에 담고,
• 자식 노드는 다음 탐색을 위해 다시 큐에 추가

하는 구조를 이용한다.

---

3. 시간 및 공간 복잡도

• 시간 복잡도: O(n) → 모든 노드를 한 번씩 방문
• 공간 복잡도: O(n) → 큐에 최대 한 레벨의 모든 노드가 저장될 수 있음

---

4. DFS 풀이

var levelOrder = function(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const len = queue.length;
    const group = [];

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

      // 자식 노드를 큐에 추가 (다음 레벨 탐색용)
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    // 한 레벨 탐색이 끝나면 결과에 추가
    result.push(group);
  }

  return result;
};

 

정리

BFS로 각 레벨의 노드를 순서대로 방문하면서,

각 레벨이 끝날 때마다 하나의 배열로 묶어서 결과에 추가한다.

 

이 방식은 트리의 구조를 레벨 단위로 그대로 출력하기 때문에,

트리 탐색 문제 중에서도 가장 전형적인 BFS 활용 예시라고 할 수 있다.