Pythonでプレオーダートラバーサルから二分探索木（BST）を構築する方法

与えられた先行順走査（プレオーダートラバーサル）に一致する二分探索木を作成することを考えます。例えば、先行順走査が [8,5,1,7,10,12] の場合、出力は [8,5,10,1,7,null,12] となり、構築される木は以下のようになります。

アルゴリズムの考え方

先行順走査では、最初の要素が必ず根（ルート）になります。また、二分探索木の性質上、あるノードより小さい値は左部分木へ、大きい値は右部分木へ配置されます。この性質を利用し、スタックを使って祖先ノードを管理しながら木を組み立てていくのがポイントです。

手順

• root := 先行順リストの0番目の要素をノードとして作成
• stack := 空のスタックを用意し、rootをプッシュ
• 先行順リストの2番目以降の各要素 i について以下を繰り返す
  • i := 値 i を持つ新しいノードを作成
  • i の値がスタックトップの値より小さい場合
    • スタックトップノードの左の子 := i
    • i をスタックにプッシュ
  • そうでない場合
    • スタックが空でなく、スタックトップの値が i の値より小さい間、以下を繰り返す
      • last := スタックトップのノード
      • スタックからポップ
    • last ノードの右の子 := i
    • i をスタックにプッシュ
• root を返す

Pythonでの実装例

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

class Solution(object):
   def bstFromPreorder(self, preorder):
      """
      :type preorder: List[int]
      :rtype: TreeNode
      """
      root = TreeNode(preorder[0])
      stack = [root]
      for i in preorder[1:]:
         i = TreeNode(i)
         if i.val<stack[-1].val:
            stack[-1].left = i
            stack.append(i)
         else:
            while stack and stack[-1].val<i.val:
               last = stack.pop(-1)
            last.right = i
            stack.append(i)
      return root

入力例

[8,5,1,7,10,12]

出力例

[8,5,10,1,7,null,12]

計算量について

このアルゴリズムでは、各ノードは最大でも一度プッシュされ、一度ポップされるため、時間計算量は O(n)、空間計算量もスタックの深さ分の O(n) となります。先行順走査の特性とBSTの性質を組み合わせることで、非常に効率的に木を再構築できるのが特徴です。