JavaScript 트리 순회 연습: 깊이별 노드 묶기

한 파일로 실행하는 전체 정답

'use strict';

function groupLevels(root) {
  if (root == null) return [];
  const queue = [root];
  const levels = [];
  let head = 0;
  while (head < queue.length) {
    const end = queue.length;
    const level = [];
    while (head < end) {
      const node = queue[head];
      head += 1;
      level.push(node.value);
      if (node.left != null) queue.push(node.left);
      if (node.right != null) queue.push(node.right);
    }
    levels.push(level);
  }
  return levels;
}

function solve({ root }) {
  return groupLevels(root);
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: end는 이번 층의 경계입니다

바깥 반복문 시작 시 queue의 head부터 끝까지는 아직 처리하지 않은 한 깊이의 노드입니다. end를 고정하고 head < end 동안만 읽으면 자식들은 다음 반복을 위해 남습니다. 각 부모의 왼쪽을 먼저 enqueue하므로 다음 층에서도 왼쪽부터의 순서가 유지됩니다.

레벨별 배열은 매 바깥 반복에서 새로 생성합니다. 같은 배열을 비운 뒤 재사용하면 이전 층 결과까지 바뀔 수 있습니다. 값이 4인 노드가 두 번 나와도 방문 집합으로 제거하지 않는 이유는 값이 노드의 신원이 아니기 때문입니다. 트리 계약상 같은 객체를 다시 만날 필요 자체가 없습니다.

root가 null이면 큐에 넣기 전에 빈 결과를 반환합니다. 나머지 경우 각 노드는 부모에서 정확히 한 번 큐에 들어가고 정확히 한 번 값이 기록됩니다. 따라서 누락·중복 없이 모든 노드가 해당 깊이에 들어갑니다.

복잡도와 큐 메모리

n은 노드 수입니다. 모든 노드를 한 번씩 처리하므로 시간 O(n)이며, 출력 배열에는 총 n개 값이 있어 O(n) 공간이 필요합니다. 이 구현은 head만 움직이고 queue에서 처리한 항목을 제거하지 않으므로 큐 자체도 O(n)입니다. 입력 트리와 출력까지 포함한 전체 공간도 O(n)이며 폭만큼의 큐라고 축소해서 계산하지 않습니다.

출력 공간을 제외한 큐를 최대 폭 O(w)로 줄이려면 처리한 앞부분을 적절히 재사용하는 실제 큐나 층 배열 교체가 필요합니다. 단순히 head가 커진다는 사실만으로 배열 저장 공간이 회수되지는 않습니다. 이 문제에서는 최대 10000개라 단순한 누적 배열을 선택합니다.

직접 확인할 경계

null, 루트 하나, 오른쪽 자식만 이어진 트리, 값이 모두 같은 완전 이진 트리를 확인하세요. 작은 트리를 재귀 DFS로 방문하면서 깊이별 배열에 값을 누적한 독립 결과와 대조하면 큐의 층 경계와 자식 순서를 동시에 검증할 수 있습니다.