問題定義

二分木の根ノードを入力として、階層順（レベル順）にノード値を探索するアルゴリズムを実装します（各レベルでは左から右へ順にアクセス）。

解法アプローチ

標準的な手法として、キューを用いた幅優先探索（BFS）を適用します。

• キューで各階層のノードを管理
• 各反復処理で現在のキューサイズを取得（現在階層のノード数）
• ノードをデキューし、値を記録後、子ノードをエンキュー
• 階層単位で結果を収集

Java実装例

import java.util.*;

class TreeNode {
    int value;
    TreeNode leftChild;
    TreeNode rightChild;
    
    TreeNode(int value) {
        this.value = value;
    }
    
    TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
        this.value = value;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

class TreeTraversal {
    public List<List<Integer>> traverseByLevel(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) return resultList;

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        while (!nodeQueue.isEmpty()) {
            int currentLevelNodes = nodeQueue.size();
            List<Integer> currentLevelValues = new ArrayList<>();

            for (int i = 0; i < currentLevelNodes; i++) {
                TreeNode currentNode = nodeQueue.remove();
                currentLevelValues.add(currentNode.value);

                if (currentNode.leftChild != null) {
                    nodeQueue.add(currentNode.leftChild);
                }
                if (currentNode.rightChild != null) {
                    nodeQueue.add(currentNode.rightChild);
                }
            }
            resultList.add(currentLevelValues);
        }
        return resultList;
    }
}

計算量分析

• 時間計算量: O(n)（全ノードのエンキュー/デキュー各1回）
• 空間計算量: O(n)（最悪ケースで最下層の全ノードを保持）

データ構造の選択理由

実装上の選択

1. Queue<TreeNode> nodeQueue = new LinkedList<>()
   • 先頭/末尾操作が高速なLinkedListが必須
2. List<List<Integer>> resultList = new ArrayList<>()
   • 追加のみで参照頻度が高いためArrayListが最適

キュー操作メソッド

• add(): 末尾への要素追加
• remove(): 先頭要素の取得と削除