Pythonで前順走査と中間順走査の結果から二分木を構築する方法

二分木の中間順走査（inorder）と前順走査（preorder）の結果が与えられたとき、それらをもとに元の二分木を復元することを考えます。

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

アルゴリズムの考え方

この問題は再帰を使うことで簡潔に解けます。鍵となるのは以下の2つの性質です。

• 前順走査の最初の要素は必ず根（ルート）である
• 中間順走査において、ルートより左側の要素は左部分木、右側の要素は右部分木に属する

処理の手順

1. buildTree メソッドに前順走査リスト（preorder）と中間順走査リスト（inorder）を渡します。
2. preorder の先頭要素を取り出してルートノードとし、preorder からその要素を削除します。
3. inorder 内でルートの値が位置するインデックス（root_index）を求めます。
4. 左の子には、inorder の 0 〜 root_index - 1 の範囲を渡して buildTree を再帰呼び出しした結果を設定します。
5. 右の子には、inorder の root_index + 1 〜 末尾までの範囲を渡して buildTree を再帰呼び出しした結果を設定します。

実装例

以下に 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, preorder, inorder):
        if inorder:
            root = TreeNode(preorder.pop(0))
            root_index = inorder.index(root.data)
            root.left = self.buildTree(preorder,inorder[:root_index])
            root.right = self.buildTree(preorder,inorder[root_index+1:])
            return root
ob1 = Solution()
print_tree(ob1.buildTree([3,9,20,15,7], [9,3,15,20,7]))

入力

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

出力

9, 3, 15, 20, 7,

計算量と最適化のヒント

この実装では、inorder.index() による線形探索が再帰のたびに行われるため、木が偏っている場合の最悪時間計算量は O(n²) になります。あらかじめ「値 → インデックス」の対応を辞書（ハッシュマップ）に記録しておけば、探索を O(1) にでき、全体を O(n) まで高速化できます。また、pop(0) やスライス操作も O(n) のコストがかかるため、大規模な入力を扱う場合はインデックスを管理する方式へ書き換えるのが効果的です。