木の走査
01 / 一文での本質
木の走査アルゴリズムはどれも各ノードをちょうど 1 回ずつ訪れる —— 違うのは、子への再帰的下降のうちで「訪問」がいつ起こるか、その一点だけ。
問題指定の順序で二分木を走査する二分木[1, 2, 3, 4, 5, ·, 6]順序前順
出力—— まだ何もない ——
深さ優先 —— 前順はノードを子への再帰の前に訪れる。
ステップ
0 / 7
訪問中
—
訪問済み
0 / 6
順序
前順
0 / 7
02 / パターンの骨格
# 深さ優先 —— 3 つの変種は「訪問」の位置だけが違うtraverse(node):if node is null: returnvisit(node) // 前順traverse(node.left)visit(node) // 中順traverse(node.right)visit(node) // 後順# 幅優先 —— 反復、キューを使うlevel_order(root):q ← [root]while q not empty:node ← q.dequeue(); visit(node)enqueue node.left, node.right
03 / このパターンを使うべき合図
「BST の中順」
二分探索木のソート済み出力は中順から生まれる —— これは BST の性質であって、中順一般の性質ではない。
「階層ごと」
木を行ごとに処理する必要があるとき —— ノードの深さ、ジグザグ出力、 「右側のビュー」など。キューによる階層順が道具。
「ボトムアップ / 子が先」
子の答えがわからないと親の答えを決められない場合 —— 部分木の和、高さ、経路など。後順なら子が先に訪れることが保証される。
「シリアライズ / 複製」
木の文字列表現を作る、あるいはノードごとに複製する。多くは明示的な null マーカー付きの前順 —— これで構造を曖昧さなく表せる。
04 / よくある落とし穴
i.
後順が必要なときに中順を使う。
子の答えから親の答えを計算するもの —— 部分木の和、高さ、直径 —— は 必ず親より前に子を訪れる必要がある。それが後順。 中順では一部の子が訪れるのが遅すぎる。
ii.
null チェックを忘れる。
再帰走査の最初の行が
if node is null: return。 これを抜くと、葉ノードの存在しない子ごとに null を参照してしまう。 アニメーションではこれを明示している —— 空の部分木はそもそも描かれない。iii.
呼び出しスタックを出力の順序と混同する。
再帰の自然な呼び出しスタックは訪問の順序ではない。 1 つのノードは前順訪問の前から後順訪問の後までスタックに乗っている —— 同じノードの 3 つの異なる「瞬間」。
05 / LeetCode で練習
4 問。最初の 3 問が DFS の定番。4 問目で BFS に引き上げられ、 階層順の真価が問われる。