Pythonのスタックを使って後順走査（ポストオーダー）から二分探索木（BST）を構築する方法

問題概要

二分探索木（BST）の後順走査（ポストオーダートラバーサル）の結果が1つ与えられたとき、その走査結果から元となる二分探索木を復元する問題を考えます。

例えば、入力が [6, 12, 10, 55, 45, 15] の場合、出力される木構造は次のようになります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 関数 solve() を定義します。引数として後順走査のリスト postorder を受け取ります。

• n := postorder の要素数とします。

• root := 後順走査の最後の要素を値として持つ新しいツリーノードを作成します。

• stk := 空のスタックを用意します。

• root をスタックにプッシュします。

• i := n - 2 とします。

• i >= 0 の間、以下の処理を繰り返します。

  • x := 値 postorder[i] を持つ新しいノードを作成します。

  • スタックが空でなく、かつ postorder[i] がスタックの先頭ノードの値より小さい間、次を繰り返します。

    • temp := スタックの先頭ノード

    • スタックから先頭要素をポップ（削除）します。

  • temp が null でない場合は、temp.left := x とします。

  • それ以外の場合は、スタックの先頭ノードの右側に x を設定します。

  • x をスタックにプッシュします。

  • i := i - 1 とします。

• root を返します。

• メイン側では、solve(postorder) の結果を返すだけで完了です。

なぜこの方法が機能するのか

後順走査では「左部分木 → 右部分木 → 根」の順にノードを訪問します。したがって、配列の最後の要素が必ず木全体の根になります。さらに、配列を末尾から先頭へ向かって処理すると、まず根から右端の経路に沿ったノード群が現れ、その後に小さな値（左部分木のノード）が出現します。スタックを使うことで、「どのノードの子として接続すべきか」という判断を効率的に行えます。各ノードがスタックに出入りするのは高々2回なので、時間計算量は O(n) と非常に効率的です。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

class TreeNode:
    def __init__(self, data = 0):
        self.val = data
        self.left = None
        self.right = None

def solve(postorder):
    n = len(postorder)
    root = TreeNode(postorder[n - 1])
    stk = []
    stk.append(root)
    i = n - 2
    while ( i >= 0):
        x = TreeNode(postorder[i])
        temp = None
        while (len(stk) > 0 and postorder[i] < stk[-1].val) :
            temp = stk[-1]
            stk.pop()
        if (temp != None):
            temp.left = x
        else:
            stk[-1].right = x
        stk.append(x)
        i = i - 1
    return root

def build_tree(postorder):
    return solve(postorder)

def inord( node):
    if node:
        inord(node.left)
        print( node.val, end = " ")
        inord(node.right)

postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print( "Inorder traversal:", end = " ")
inord(root)

入力

[6, 12, 10, 55, 45, 15]

出力

6 10 12 15 45 55

まとめ

復元された木に対して中順走査（インオーダートラバーサル）を行うと、6 10 12 15 45 55 という昇順の結果が得られます。これは二分探索木の性質（中順走査すると昇順に並ぶ）と一致しており、正しく木が復元できたことが確認できます。スタックを活用したこの手法は、再帰呼び出しを使わずに線形時間で BST を構築できる優れたアプローチです。