Pythonで中順・後順走査の結果から二分木を再構築する方法

二分木の中順走査（inorder）と後順走査（postorder）の結果が与えられているとします。これらの走査結果をもとに、元の二分木を復元することを考えます。たとえば、後順走査が [9,15,7,20,3]、中順走査が [9,3,15,20,7] の場合、構築される木は次の図のようになります。

この問題を解く鍵は、後順走査の最後の要素が必ず木のルートになるという性質です。さらに、中順走査においてそのルートより左側にある要素は左部分木に、右側にある要素は右部分木に属します。この性質を再帰的に適用することで、木全体を組み立てることができます。

アルゴリズムの手順

build_tree() メソッドを定義し、中順走査リスト inorder と後順走査リスト postorder を引数として受け取ります。

• 中順リストが空でない場合、以下を実行します。

  • root := 後順リストの末尾の値でノードを作成し、その要素をリストから取り除く（pop）

  • ind := 中順リスト内での root のデータのインデックス位置

  • root の右の子 := build_tree(inorder[ind+1:], postorder) — 右部分木を先に構築

  • root の左の子 := build_tree(inorder[:ind], postorder) — 左部分木を構築

• root を返す

ここで重要なのは、右部分木を先に構築する点です。後順走査は「左 → 右 → 根」の順でノードを訪問するため、リストの末尾から取り出すと「根 → 右 → 左」の順になります。つまり、pop() で取り出した直後の要素は、必ず右部分木のノードに対応するのです。

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()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

入力

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

出力

[9,3,15,20,7]

計算量と改善のヒント

この実装では、各再帰呼び出しのたびに inorder.index() でルートの位置を線形探索しているため、最悪の場合の時間計算量は O(n²) となります。事前に「値 → インデックス」の対応を辞書（ハッシュマップ）に記録しておけば、位置の検索を O(1) で行えるようになり、全体の計算量を O(n) まで改善できます。要素数が多い木を扱う場合は、この最適化を検討するとよいでしょう。