レベル順走査 — 木の幅優先探索
レベル順（BFS）木走査を学びます。上から下へ層ごとにノードを訪問します。キューベースのアルゴリズム、レベルグループ化、ジグザグ変形を理解します。
Traversal
詳細な説明
レベル順走査（BFS）
レベル順走査は上から下へ、各レベル内で左から右へ、レベルごとにノードを訪問します。3つの深さ優先走査（通りがけ順、行きがけ順、帰りがけ順）とは異なり、レベル順はスタックや再帰ではなくキューを使用します。
アルゴリズム
LEVELORDER(root):
if root is NULL: return
queue = [root]
while queue is not empty:
node = queue.dequeue()
visit(node)
if node.left: queue.enqueue(node.left)
if node.right: queue.enqueue(node.right)
例
4
/ \
2 6
/ \ / \
1 3 5 7
レベル順結果: [4, 2, 6, 1, 3, 5, 7]
レベル 0: [4]
レベル 1: [2, 6]
レベル 2: [1, 3, 5, 7]
レベルグループ化変形
ノードをレベルごとにグループ化するには、各レベルの開始時にキューサイズを追跡します。
結果: [[4], [2, 6], [1, 3, 5, 7]]
ジグザグレベル順
人気のある面接変形は各レベルで方向を交互にします：レベル 0 は左から右、レベル 1 は右から左、以下同様。グループ化出力の1つおきのレベルを反転することで解決されます。
時間・空間計算量
- 時間: O(n) — すべてのノードが1回訪問される
- 空間: O(w) — w は木の最大幅（最も広いレベル）。完全二分木では O(n/2) = O(n)
ユースケース
レベル順走査は重み無しグラフでの最短経路の発見（BFS が標準アルゴリズム）、ストレージ用の木のシリアライゼーション（null マーカー付きレベル順）、デバッグ用の木構造の層ごとの出力、「二分木の最小の深さ」や「二分木の右側ビュー」などの問題解決に使用されます。