Pythonで後順走査（ポストオーダー）の結果から二分探索木を構築する方法

二分探索木（BST）の後順走査（ポストオーダー走査）の結果が与えられたとき、そのシーケンスから元の木を復元する方法を解説します。

例えば、後順走査の結果が [9,15,7,20,3] である場合、構築される木は次のようになります。

基本となる考え方

通常、木を一意に復元するには中順走査（インオーダー走査）の結果も必要です。しかし、二分探索木では中順走査の結果が必ず昇順にソートされた順序になるという重要な性質があります。この性質を利用すれば、後順走査の結果だけで木を構築できます。

アルゴリズムの手順

• 中順走査のリスト = 後順走査のリストをソートしたもの として求める
• build_tree() メソッドを定義し、inorder（中順）と postorder（後順）を引数として受け取る
• inorder リストが空でない場合、以下を実行する
  • root := postorder の末尾の値でノードを作成し、その要素をリストから削除する
  • ind := inorder リスト内での root のデータのインデックス位置
  • root の右部分木 := build_tree(inorder[ind+1:], postorder) を呼び出して構築
  • root の左部分木 := build_tree(inorder[:ind], postorder) を呼び出して構築
• root を返す

実装例

それでは、実際のPythonコードを見てみましょう。

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

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution(object):
    def buildTree(self, inorder, postorder):
        if inorder:
            root = TreeNode(postorder.pop())
            ind = inorder.index(root.data)
            root.right = self.buildTree(inorder[ind+1:], postorder)
            root.left = self.buildTree(inorder[:ind], postorder)
            return root

ob1 = Solution()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

入力

[9,3,15,20,7]
[9,15,7,20,3]

出力

[3,7,9,15,20]

ポイントの解説

このアルゴリズムの鍵となるのは、後順走査では「左部分木 → 右部分木 → 根」の順でノードが訪問される点です。つまり、リストの末尾の要素が必ず根になります。

また、pop() で末尾から順に取り出すため、右部分木を先に構築してから左部分木を構築する必要がある点にも注意してください。これは、後順走査のリストを末尾から見ていくと「根 → 右部分木 → 左部分木」の順で現れるためです。

計算量についても触れておくと、各ノードで index() による線形探索を行うため、時間計算量は O(n²) となります。ハッシュマップで値からインデックスへの対応を事前に構築しておけば、O(n) まで改善可能です。