帰りがけ順走査 — 左、右、ルート

帰りがけ順走査（LRN）

帰りがけ順走査は 左部分木、右部分木、ノード の順序でノードを訪問します。ルートは常に出力の最後の要素であり、子を親の前に処理する必要がある操作の自然な順序です。

再帰的実装

POSTORDER(node):
  if node is NULL: return
  POSTORDER(node.left)
  POSTORDER(node.right)
  visit(node)          // ルートを最後に処理

例

        4
       / \
      2   6
     / \ / \
    1  3 5  7

帰りがけ順結果: [1, 3, 2, 5, 7, 6, 4]

リーフが最初に訪問され（1, 3, 5, 7）、次に内部ノードがボトムアップで、ルート（4）が最後です。

なぜ帰りがけ順で削除するのか？

木全体を削除する場合、ダングリング参照を避けるために子を親の前に解放する必要があります。帰りがけ順走査は自然に子を最初に訪問します：

DELETE_TREE(node):
  if node is NULL: return
  DELETE_TREE(node.left)   // まず左部分木を解放
  DELETE_TREE(node.right)  // 次に右部分木を解放
  free(node)               // 最後にノード自体を解放

式木の評価

内部ノードが演算子でリーフがオペランドの式木では、帰りがけ順走査は**後置記法（逆ポーランド記法）**を生成します：

        *
       / \
      +   3
     / \
    1   2

帰りがけ順: [1, 2, +, 3, *] → (1 + 2) * 3 = 9

2つのスタックによる反復的実装

帰りがけ順は反復的に実装するのが最も難しい走査です。一般的なアプローチは2つのスタックを使用します。

時間・空間計算量

• 時間: O(n) — すべてのノードを1回訪問
• 空間: O(h) — 再帰の深さは木の高さに等しい