레벨 순회 (Level Order Traversal, BFS)

1. 개념

트리의 노드를 깊이(레벨) 순서대로 탐색하는 방법으로, BFS(너비 우선 탐색)과 동일
큐(Queue)를 활용해 가까운 노드부터 순서대로 처리한다.

2. 대표 문제 유형

• 레벨별 그룹화
• 최소 깊이 구하기
• 각 노드 깊이 계산

3. 예시 코드

(1) 레벨별 노드 값 저장

List<List<Integer>> bfs(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            level.add(node.value);
            queue.addAll(node.children);
        }
        result.add(level);
    }
    return result;
}

(2) 최소 깊이 구하기

int bfs(Node root) {
    Queue<Pair<Node, Integer>> queue = new LinkedList<>();
    queue.add(new Pair<>(root, 1));
    while (!queue.isEmpty()) {
        var current = queue.poll();
        Node node = current.getKey();
        int depth = current.getValue();
        if (node.children.isEmpty()) return depth; // 리프 노드
        for (Node child : node.children) {
            queue.add(new Pair<>(child, depth + 1));
        }
    }
    return 0;
}

(3) 각 노드 깊이 계산 ← 추가됨

Map<Node, Integer> bfs(Node root) {
    Map<Node, Integer> depth = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    depth.put(root, 0);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        for (Node child : node.children) {
            depth.put(child, depth.get(node) + 1);
            queue.add(child);
        }
    }
    return depth;
}

• 출제 포인트: "각 노드의 깊이" 또는 "거리" → BFS 기본 패턴

4. 출제 포인트

• “가장 가까운”, “레벨별”, “거리 계산”이라는 키워드 → BFS 가능성 높음
• 루트 기준 거리, 최단 거리 → BFS가 훨씬 자연스럽고 빠름
• 큐에 (노드, 깊이) 또는 (노드, 상태) 같이 필요한 정보를 함께 넣기

 

 

[LeetCode 104] Maximum Depth of Binary Tree → BFS로 최대 깊이 구하기

[LeetCode 111] Minimum Depth of Binary Tree → BFS로 최소 깊이 구하기

[프로그래머스] 게임 맵 최단거리 → BFS 거리 계산 패턴

[LeetCode 429] N-ary Tree Level Order Traversal → 레벨별 그룹화 문제