Pythonで中順走査（インオーダー）と後順走査（ポストオーダー）から二分木を構築する方法

はじめに

二分木の中順走査（インオーダー）と後順走査（ポストオーダー）の結果が分かっていれば、この2つの列を組み合わせることで元の二分木を一意に復元できます。
例として、後順走査の列が [9,15,7,20,3]、中順走査の列が [9,3,15,20,7] である場合、構築される二分木は次の構造になります。

      3
     / \
    9   20
       /  \
      15   7

アルゴリズムの手順

再帰的に木を組み立てていきます。ここではメソッド名を buildTree とし、基本の流れは以下のとおりです。

• 根の決定： 後順走査の「最後の要素」が必ず根（ルート）になります。これを取り出してノードを作成します。
• 分割点の特定： 根の値が中順走査の列のどこに位置するか（root_index）を調べます。
• 左右の分割： 中順走査において root_index より左側の要素は左部分木、右側の要素は右部分木に属します。
• 右部分木の構築： 後順走査は末尾側から消費するため、先に右部分木を再帰的に構築します。
• 左部分木の構築： 続けて左部分木を再帰的に構築します。

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())
            # 中順走査内での根の位置を特定
            root_index = inorder.index(root.data)
            # 右部分木を先に構築（末尾から消費するため）
            root.right = self.buildTree(inorder[root_index + 1:], postorder)
            # 左部分木を構築
            root.left = self.buildTree(inorder[:root_index], postorder)
            return root


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

入力

中順走査（inorder）: [9, 3, 15, 20, 7]
後順走査（postorder）: [9, 15, 7, 20, 3]

出力

9, 3, 15, 20, 7,

構築した木を中順走査で出力すると、入力として与えた中順走査の列と一致していることが確認できます。

計算量について

この実装では、再帰呼び出しごとに list.index() による線形探索とスライスによるリストコピーが発生するため、時間計算量は O(n²) となります。

要素の値からインデックスへの対応をあらかじめ辞書（ハッシュマップ）に記録しておき、スライスの代わりに開始・終了インデックスを引数として渡す方式に変更すれば、全体を O(n) まで高速化できます。大きな入力を扱う場合は、この最適化を検討するとよいでしょう。