二分木の post-order 走査
二分木の post-order 走査
このレッスンで分かること
- in-order / pre-order / post-order の違いは「根を訪問する位置」だけ
- 3 種類の走査の最後は post-order (左 → 右 → 根) です
- post-order は、子の結果を集めてから親で集約する処理に向いています
二分木の post-order 走査 とは
二分木を配列表現で受け取り、post-order (左 → 右 → 根) で訪問した値の配列を返す関数を実装する。
3 種類の走査の最後は post-order (左 → 右 → 根) です。根を 最後 に訪問するのが特徴で、「子を全部処理してから親を処理する」流れになります。in-order / pre-order と並べて書くと、result.append の位置が違うだけだと気づくはずです。
post-order = 左 → 右 → 根。子を片付けてから親を処理 したい場面で使う (ノード削除、ファイルシステムの容量集計など)。
post-order の使いどころ
post-order は、子の結果を集めてから親で集約する処理に向いています。
- 木の 解放 (delete) 子から先に消さないとメモリリークする
- ディレクトリの 総容量計算 子フォルダのサイズを足し上げて親が確定する
- 数式の 後置記法 (
a b +のような逆ポーランド記法) - 関数呼び出しの 戻り値で集約する DP や 木 DP
- HTML/XML の クローズタグ生成 (子要素を閉じてから親を閉じる)
要するに 「下から積み上げる」 性質を持つ問題には post-order が自然です。再帰の戻り値で何かを返すアルゴリズム (例えば「木の高さ」や「最大経路和」) は、必ず post-order の形になります。
例で理解する
[1, 2, 3, null, 4] の木を post-order で走査します。
- 左部分木
2の post-order- 左
null(skip) - 右
4の post-order →[4] - 根
2→[4, 2]
- 左
- 右部分木
3(子なし) →[3] - 最後に根
1を追加 →[4, 2, 3, 1]
結果は [4, 2, 3, 1]。1 が 一番最後 に出ているのが post-order の典型です。逆に言えば、結果の 末尾が根 になっているかを見れば post-order だと判別できます。
in-order / pre-order / post-order の違いは「根を訪問する位置」だけ。3 つを並べて書き比べると一目瞭然になる。
Python での実装
Python
def postorder(tree):
result = []
def visit(i):
if i >= len(tree) or tree[i] is None:
return
visit(2 * i + 1)
visit(2 * i + 2)
result.append(tree[i])
visit(0)
return result再帰の 左 → 右 → 根 の順序がそのままコードに現れています。result.append を 最後 に置くのがポイントです。visit(2*i+1) が左、visit(2*i+2) が右、最後に result.append(tree[i]) で自分自身を訪問、という 3 ステップです。
JavaScript での実装
JavaScript
function postorder(tree) {
const result = [];
const visit = (i) => {
if (i >= tree.length || tree[i] === null) return;
visit(2 * i + 1);
visit(2 * i + 2);
result.push(tree[i]);
};
visit(0);
return result;
}post-order と DP の関係
次のレッスンで実装する「木の高さ」は post-order そのものです。
Python
def height(tree, i=0):
if i >= len(tree) or tree[i] is None:
return 0
return 1 + max(height(tree, 2*i+1), height(tree, 2*i+2))左右の高さを再帰で取得してから親で max + 1 を返す、というのは典型的な post-order の流れです。「子の戻り値を見てから親を計算する」 タイプの再帰は、ほぼすべて post-order です。
後の章で出てくる「BST の妥当性チェック」「最大経路和」「最大独立集合 (House Robber III)」なども、すべて post-order の 木 DP で書けます。
木 DP の本体は post-order。「子の
dp[child]から親のdp[node]を作る」流れが頭に染み込めば、難しい木問題も恐くなくなる。
よくある間違い
1 つ目は 根を真ん中に置いてしまう。それは in-order です。visit(left) → visit(right) → 根 の順序を厳守してください。2 つ目は 右の再帰を忘れる。左しか書かないと「左連鎖」だけ取って終わってしまいます。3 つ目は 空チェックを忘れる。再帰の基底ケースは「範囲外 or None」の両方が必要です。
やってみよう
[1, 2, 3]を post-order で走査すると[2, 3, 1]。in-order の[2, 1, 3]と比較する。- 完全二分木
[1, 2, 3, 4, 5, 6, 7]を post-order すると[4, 5, 2, 6, 7, 3, 1]。 - 反復版を書くと意外と難しい。「pre-order の
根 → 右 → 左」を逆順に並べる とトリッキーに解ける。挑戦してみよう。 - ディレクトリ構造を post-order で走査して 総容量 を計算するスクリプトを書いてみる。
「ファイルシステムの容量を計算する」シチュエーションを想像すれば post-order の必然性が見えてくる。
よくある質問
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 つができることを確認しましょう。
- post-order 走査 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. post-order 走査 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 再帰または反復で left -> right -> root の順に訪問する
- 戻り値は訪問順の値の配列。null は結果に含めない
入出力例
test-cases.txt
postorder([1,2,3,null,4]) → [4,2,3,1]
postorder([1]) → [1]
postorder([1,2,3]) → [2,3,1]
postorder([1,null,2,null,null,null,3]) → [3,2,1]
postorder([1,2,3,4,5,6,7]) → [4,5,2,6,7,3,1]
postorder([5,3,8,1,4,null,9]) → [1,4,3,9,8,5]