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

읽기 전에 알아두면 좋아요

아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.

트리 자료구조 차이: 이진 트리 BST MST 구분하기트리는 노드가 부모와 자식으로 연결된 구조입니다. 연결을 따라 읽는 방법을 확인합니다. 트리의 깊이와 큐의 층별 방문 순서를 연결합니다.
큐와 FIFO: head 인덱스로 JavaScript 대기열 만들기큐는 먼저 넣은 값을 먼저 꺼냅니다. 대기열에 넣고 꺼낼 때의 순서를 확인합니다. 먼저 들어온 값을 먼저 꺼내는 큐의 동작을 확인합니다.

개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.

과정 위치와 선택 복습 안내

과정 위치: 트리·그래프와 최단거리 · 문제

과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.

JavaScript로 문법·실행 복습하기 (선택)

개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.

이진 트리의 노드를 깊이별로 묶는 문제는 어떤 결과를 반환하나요?

트리의 노드를 깊이별로 묶은 배열을 반환하는 문제입니다. 트리·깊이·큐의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.

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

본문 근거: Binary Tree Level Order Traversal · Princeton — Binary Search Trees

독립 창작 문제

이 문제의 상황·입출력 계약·예시는 이 글을 위해 직접 구성했습니다. 공식 문제를 번역하거나 복제한 지문이 아닙니다. 구현 개념은 트리 자료구조 차이: 이진 트리 BST MST 구분하기에서 먼저 확인할 수 있습니다.

이진 트리가 주어집니다. 루트의 깊이를 0으로 정하고 같은 깊이의 노드 값을 왼쪽부터 묶어 배열로 반환하세요. 값이 같아도 서로 다른 노드이면 모두 포함합니다. 빈 트리의 결과는 빈 배열입니다.

여기서 왼쪽부터란 부모를 왼쪽부터 처리하면서 각 부모의 왼쪽 자식, 오른쪽 자식 순으로 읽는 것을 뜻합니다. 노드 값의 숫자 크기로 정렬하면 안 됩니다. 깊이가 커질수록 바깥 배열의 뒤에 한 줄씩 추가합니다.

입력·출력과 제약

표준 입력은 {root} 형태의 JSON 객체입니다. root는 null 또는 {value,left,right} 노드입니다. value는 안전 정수이고 없는 자식은 null 또는 필드 생략으로 표현합니다. 노드 수는 0~10000, 루트부터의 최대 깊이는 200입니다. 각 노드는 부모를 최대 하나만 갖는 유효한 트리이며 사이클과 공유 노드는 없습니다.

표준 출력은 [[깊이0의 값들],[깊이1의 값들],…] 형태의 JSON 배열입니다. 빈 깊이를 중간에 따로 만들지 않습니다. JSON은 객체 참조를 공유하는 형식이 아니며 코드의 반복 순회가 깊은 객체를 지원하더라도 입출력 직렬화 한도를 무한히 보장하지 않으므로 위 깊이 제약을 따릅니다.

입력 예시

{"root":{"value":7,"left":{"value":4,"right":{"value":4}},"right":{"value":9}}}

출력 예시

[[7],[4,9],[4]]

실행 방법

Node.js CommonJS 환경에서 정답의 전체 코드를 tree-problem.cjs로 저장합니다. 입력 예시를 UTF-8 input.json 파일로 저장한 뒤 Windows PowerShell에서는 아래 명령을 실행하세요. 내장 node:fs 외에 다른 파일이나 패키지가 필요하지 않습니다.

Get-Content -Raw -Encoding UTF8 ./input.json | node ./tree-problem.cjs

macOS·Linux의 Bash에서는 아래 입력 리다이렉션을 사용할 수 있습니다. 이 < 문법은 PowerShell 명령이 아닙니다.

node ./tree-problem.cjs < input.json

힌트

한 층을 시작할 때 queue.length를 end에 저장하세요. 그 층을 처리하면서 새 자식이 뒤에 추가되어도 head가 end에 도달하면 반드시 현재 층을 끝냅니다. 반복 조건에 계속 바뀌는 queue.length를 쓰면 모든 깊이가 한 줄로 합쳐집니다.

직접 풀어보기

먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.

내 풀이 JavaScript0 / 6,000바이트

function solve(input) {
    // 아래 함수 계약에 맞게 결과를 반환하세요.
    return [];
}

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다. Tab은 다음 항목으로 이동합니다. 입력 영역 오른쪽 아래를 끌어 높이를 조절할 수 있습니다.

비밀키·개인정보는 입력하지 마세요. 코드는 이 페이지에만 유지됩니다.

해답·해설 보기

'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);
}

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다.

from collections import deque
def solve(input):
    root=input['root']
    if root is None: return []
    q, out=deque([root]), []
    while q:
        level=[]
        for _ in range(len(q)):
            node=q.popleft()
            level.append(node['value'])
            for side in ('left','right'):
                if node.get(side) is not None: q.append(node[side])
        out.append(level)
    return out

원문 JSON 객체를 파싱한 dict input을 solve(input)에 전달하고 list를 반환합니다. 표준 입출력은 포함하지 않습니다.

import java.util.*;
class Solution {
    static class Node {
        long value;
        Node left, right;
        Node(long v) {
            value = v;
        }
    }
    public long[][] solve(Node root) {
        List < long[] > out = new ArrayList < >();
        if (root == null) return new long[0][];
        Queue < Node > q = new ArrayDeque < >();
        q.add(root);
        while (! q.isEmpty()) {
            int size = q.size();
            long[] row = new long[size];
            for (int i = 0; i < size; i++) {
                Node n = q.remove();
                row[i] = n.value;
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            out.add(row);
        }
        return out.toArray(new long[0][]);
    }
}

Solution.Node로 value,left,right를 구성하고 solve(root)를 호출해 long[][] 반환. null 루트 허용.

#include <queue>
#include <vector>
struct Node {
    long long value;
    Node * left = nullptr;
    Node * right = nullptr;
    explicit Node(long long v) : value(v) {
    }
};
std::vector < std::vector < long long >> solve(Node * root) {
    std::vector < std::vector < long long >> out;
    if (! root) return out;
    std::queue < Node * > q;
    q.push(root);
    while (! q.empty()) {
        int size = q.size();
        std::vector < long long > row;
        while (size--) {
            Node * n = q.front();
            q.pop();
            row.push_back(n->value);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        out.push_back(row);
    }
    return out;
}

Node* root를 전달해 64비트 정수 2차원 벡터 반환. 입력 노드는 호출자 소유이며 변경하지 않습니다. C++11 이상.

using System.Collections.Generic;
public class Solution {
    public class Node {
        public long value;
        public Node left, right;
        public Node(long v) {
            value = v;
        }
    }
    public long[][] Solve(Node root) {
        var result = new List < long[] >();
        if (root == null) return result.ToArray();
        var q = new Queue < Node >();
        q.Enqueue(root);
        while (q.Count > 0) {
            int size = q.Count;
            var row = new long[size];
            for (int i = 0; i < size; i++) {
                Node n = q.Dequeue();
                row[i] = n.value;
                if (n.left != null) q.Enqueue(n.left);
                if (n.right != null) q.Enqueue(n.right);
            }
            result.Add(row);
        }
        return result.ToArray();
    }
}

Solution.Node로 원문 트리를 구성하고 Solve(root)를 호출해 long[][] 반환. null 루트 허용.

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

'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하므로 다음 층에서도 왼쪽부터의 순서가 유지됩니다.

바깥 반복 시작	head	end	이번 결과	다음에 추가되는 값
루트 7	0	1	[7]	4,9
두 번째 층	1	3	[4,9]	4
세 번째 층	3	4	[4]	없음

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

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

복잡도와 큐 메모리

풀이 직접 실행

본문 풀이에 예제 입력을 넣고, 입력을 바꿔 계산 결과를 비교합니다.

예제 크게 보기 (새 탭)

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

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

직접 확인할 경계

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

함께 연습하고 확인할 자료

Binary Tree Level Order Traversal: 이진 트리를 레벨 순서로 방문하는 외부 연습입니다. 플랫폼의 노드 형식과 제출 인터페이스는 공식 페이지에서 확인하세요.

관련 개념 참고: Princeton Algorithms — Minimum Spanning Trees, Princeton — Binary Search Trees, BlogFlow — 기존 트리 자료구조 글 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.

이 문제를 푼 뒤 확인하기

노드가 하나인 트리와 자식이 여러 수준에 걸친 트리에서 깊이별 묶음을 그려 보세요.

본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.

글 소개·학습 준비·전체 목차

트리의 계층 구조와 순회를 표현한 개념 표지 — 구조의 특징을 표현한 개념 이미지입니다. 정확한 동작은 아래 코드와 추적 표를 함께 확인하세요.

핵심 요약

이진 트리의 노드를 깊이별로 묶되 같은 깊이에서는 왼쪽부터 출력합니다. 큐의 현재 층 경계를 고정해 다음 층이 섞이지 않게 하는 독립 창작 문제입니다.

이 글이 도움이 되었나요?

조회 중

이어서 공부하기

체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 층별 방문 순서와 최솟값 추출을 추적하고, 다익스트라의 비음수 조건과 오래된 후보를 설명하세요.

다음 추천 · 자료구조 개념: JavaScript 이진 탐색 트리 구현: 중복 키와 세 가지 삭제 처리

같은 주제에서 다음 개념과 예제로 이해를 넓힙니다.

권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.

원래 과정 목록 순서 (선택)

읽음 기록

읽음 — / 전체 58개 · 필수 58개

이 글을 쓴 해비

웹사이트를 제작·운영하고, 개인 서비스와 자동화·AI 도구를 만듭니다. 직접 만들며 배운 내용과 문제 해결 과정을 BlogFlow에 기록합니다.

새 글 받아보기

RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.

RSS 피드 구독하기