【C++】二分探索木の先行順走査（プレオーダー）列の妥当性を検証するアルゴリズム

数値のシーケンスが与えられたとき、それがある二分探索木（BST）の正しい先行順走査（プレオーダートラバーサル）の結果であるかどうかを判定する問題を考えてみましょう。ここでは、シーケンス内の各数値はすべて一意であるものと仮定します。

例として、次のような二分探索木を想定します。

この木の場合、入力が [5,2,1,3,6] であれば、出力は true になります。

解法のアプローチ

この問題は、スタックによるシミュレーションを用いることで効率的に解くことができます。手順は以下の通りです。

• itr := -1（スタックのトップ位置を表すインデックス）

• low := -∞（これまでに確定した下限値）

• i := 0 から preorder のサイズ未満まで、i を1ずつ増やしながら以下を繰り返す：

  • x := preorder[i]

  • x < low であれば、false を返す

  • itr ≥ 0 かつ preorder[itr] < x の間、以下を繰り返す：

    • low := preorder[itr]

    • itr を1減らす

  • itr を1増やす

  • preorder[itr] := x

• true を返す

アルゴリズムのポイント

先行順走査では、最初の要素が根となり、続いて左部分木の全要素、その後ろに右部分木の全要素が並びます。二分探索木の性質上、あるノードより小さい値はすべてその左部分木に、大きい値はすべて右部分木に含まれます。

そこで、スタック（ここでは配列の先頭部分を再利用）に現在たどっている経路上のノードを保持します。新しい値 x がスタックトップより大きい場合、x はそれらのノードの右側の部分木に属することを意味するため、スタックから値を取り出しながら下限 low を更新していきます。最終的に x が low よりも小さければ、BST の構造と矛盾するため false を返します。

この手法により、時間計算量 O(n)・空間計算量 O(n) で検証が可能です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool verifyPreorder(vector<int>& preorder) {
      int itr = -1;
      int low = INT_MIN;
      for (int i = 0; i < preorder.size(); i++) {
         int x = preorder[i];
         if (x < low)
            return false;
         while (itr >= 0 && preorder[itr] < x) {
            low = preorder[itr];
            itr--;
         }
         itr++;
         preorder[itr] = x;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,2,1,3,6};
   cout << (ob.verifyPreorder(v));
}

入力

{5,2,1,3,6}

出力

1