二分木の幅優先走査 (BFS)
二分木の幅優先走査 (BFS)
このレッスンで分かること
- ショートカット解は美味しいが、本質を学ぶならキューを使った BFS を書こう
- Python では
collections.dequeを使うとpopleft()が O(1) で動きます- このレッスンで扱うのは対極にある 幅優先走査 (BFS, Breadth-First Search) です
二分木の幅優先走査 とは
二分木を配列表現で受け取り、レベル順 (BFS) で訪問した値の配列を返す関数を実装する。本レッスンでは、二分木の幅優先走査 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
ここまでの 3 つの走査 (in-order / pre-order / post-order) は、いずれも 再帰 で「深く潜ってから帰ってくる」スタイルでした。これらをまとめて 深さ優先走査 (DFS, Depth-First Search) と呼びます。
このレッスンで扱うのは対極にある 幅優先走査 (BFS, Breadth-First Search) です。BFS は「レベル (深さ) ごと に左から右へ順番に訪問する」走査で、level-order とも呼ばれます。
DFS は深く潜る、BFS は 同じ深さを横一列に 訪問する。最短経路問題はほぼ BFS が出番。
BFS のイメージ
[1, 2, 3, null, 4] の木を BFS で走査します。
図のポイント (テキスト併記)
- レベル
0に1、レベル1に2と3、レベル2に4(nullはスキップ)
レベル 0 に 1、レベル 1 に 2 と 3、レベル 2 に 4 (null はスキップ)。結果は [1, 2, 3, 4] です。
面白いことに、この木の場合は 入力の配列とほぼ同じ並び になります。これは入力配列が「BFS 順」で並んでいるためです。null を取り除いた配列 が答えになる、と言ってもよいでしょう。
入力配列は BFS 順なので、
nullを除いた配列がそのまま BFS 結果 になる。
キュー (queue) を使う実装
BFS は キュー (FIFO) を使って書くのが定石です。手順は次のとおりです。
- ルートのインデックス
0をキューに入れる - キューから 1 つ取り出す → 値を
resultに追加 → 左右の子を 存在すれば キューに入れる - キューが空になるまで 2. を繰り返す
Python
from collections import deque
def levelOrder(tree):
if not tree or tree[0] is None:
return []
result = []
queue = deque([0])
while queue:
i = queue.popleft()
if i >= len(tree) or tree[i] is None:
continue
result.append(tree[i])
queue.append(2 * i + 1)
queue.append(2 * i + 2)
return resultPython では collections.deque を使うと popleft() が O(1) で動きます。list.pop(0) だと O(n) かかるので避けてください。
JavaScript での実装
JavaScript
function levelOrder(tree) {
if (tree.length === 0 || tree[0] === null) return [];
const result = [];
const queue = [0];
while (queue.length > 0) {
const i = queue.shift();
if (i >= tree.length || tree[i] === null) continue;
result.push(tree[i]);
queue.push(2 * i + 1);
queue.push(2 * i + 2);
}
return result;
}JS の Array.shift() は O(n) ですが、テスト規模なら問題ありません。本番では [head, ...] を使った deque 実装に置き換えるのが定石です。
もう 1 つの実装 (配列フィルタ)
入力が BFS 順の配列 で渡されている前提なら、わざわざキューを回さずとも null を除外するだけで答えになります。
Python
def levelOrder(tree):
return [v for v in tree if v is not None]この実装は null が子スロットを占有しない密な BFS 順 の入力にしか対応できません。キュー版はヒープ式インデックス (2 * i + 1 / 2 * i + 2) を使うため、null も固定スロットを占有する前提で動いており、両者は入力形式の前提が異なります。例えば [1, null, 3] のような内部に欠損ノードを含む木では、フィルタ版は [1, 3] を返しますが、キュー版も [1, 3] を返すように見えて、より深い木では食い違いが生じます。フィルタ版は一般解ではないため、面接の場では「キューを使った定石」を書いた方が評価されます。
ショートカット解は美味しいが、本質を学ぶならキューを使った BFS を書こう。
BFS の応用
BFS の真価は 最短経路 にあります。重みのない辺で「スタートから各ノードへの最短ステップ数」を求めたいなら、ほぼ無条件で BFS です。第 5 章のグラフでも再登場します。
他にも次のような応用があります。
- 木のレベルごとに値を分ける (
[[1], [2, 3], [4]]のような構造) - 二分木の右側のビュー (各レベルの一番右の値だけ取り出す)
- ジグザグ走査 (レベルごとに左→右と右→左を交互に切り替える)
よくある間違い
1 つ目は スタックと混同する。DFS はスタック (LIFO)、BFS はキュー (FIFO) です。LIFO で書くと深さ優先になってしまいます。2 つ目は null の子をキューに入れて取り出すときに値を追加してしまう。取り出した後に None チェックを入れて continue するのが安全です。3 つ目は list.pop(0) の O(n)。Python は deque を使うのが鉄則です。
やってみよう
[1, 2, 3, 4, 5, 6, 7]を BFS で走査して[1, 2, 3, 4, 5, 6, 7]になることを確認する。- レベルごとに分けた配列
[[1], [2,3], [4,5,6,7]]を返す版を書いてみる。for _ in range(len(queue))のテクニックを使う。 - 「木の最大幅 (level に存在するノード数の最大)」を BFS で計算してみる。
BFS と DFS は CS の双璧。どちらも息をするように書けるようになると、グラフ問題の 8 割は片付く。
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 二分木の高さ で、各ノードの深さの最大値を再帰や BFS を用いて求める方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BFS 走査 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BFS 走査 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- キュー (FIFO) を使ってレベル順に訪問する
- 戻り値は訪問順の値の配列。null は結果に含めない
入出力例
test-cases.txt
levelOrder([1,2,3,null,4]) → [1,2,3,4]
levelOrder([1]) → [1]
levelOrder([1,2,3]) → [1,2,3]
levelOrder([1,null,2,null,null,null,3]) → [1,2,3]
levelOrder([1,2,3,4,5,6,7]) → [1,2,3,4,5,6,7]
levelOrder([5,3,8,1,4,null,9]) → [5,3,8,1,4,9]