C++でBSTを構築せずに2つの配列が同一の二分探索木になるか判定する方法

ここでは、2つの配列がそれぞれBST(二分探索木)への挿入順序を表しているものとします。各配列の要素を左から右へ順に取り出してBSTを構築したとき、両者から同じ形の木ができるかどうかを判定します。ただし、実際にBSTを構築することは禁止されています。例えば、配列 {2, 4, 1, 3} と {2, 1, 4, 3} が与えられた場合、この2つの列はどちらも同じBSTを生成することが分かります。

アプローチはシンプルです。BSTには「根より小さい要素は左部分木に、根より大きい要素は右部分木に属する」という基本的な性質があります。したがって、2つの配列が同じBSTを表すためには、任意の要素 x について、x の左部分木・右部分木に属する要素が、両方の配列で必ず x より後ろに現れている必要があります。この性質は、左部分木・右部分木の根についても同様に成り立ちます。

具体的には、両方の配列の中で「次に現れる小さい側の要素」と「次に現れる大きい側の要素」が一致しているかを確認し、このチェックを左部分木と右部分木に対して再帰的に適用していきます。

アルゴリズムの流れ

• 各再帰呼び出しでは、min〜max の範囲に収まる最初の要素を、両方の配列の未処理部分から線形探索で見つけます。
• 片方の配列にしか候補が存在しない場合や、見つかった要素の値が一致しない場合は false を返します。
• 両方の配列で範囲内の要素が見つからなければ、その部分木は葉であると判断して true を返します。
• 見つかった要素を新しい根とみなし、その値を境界として右部分木(tree1[j]〜max)と左部分木(min〜tree1[j])に対して再帰的に同じ処理を続けます。

なお、各再帰呼び出しで線形探索を行うため、最悪の場合の計算量は O(n²) となります。実際にBSTを構築して比較する O(n log n) の手法より遅くなる可能性がありますが、「木を構築してはならない」という制約条件下では有効なアプローチです。

C++での実装例

#include <iostream>
using namespace std;
bool isSameCheckHelper(int tree1[], int tree2[], int n, int i1, int i2, int min, int max) {
    int j, k;
    for (j = i1; j < n; j++)
        if (tree1[j] > min && tree1[j] < max)
            break;
    for (k = i2; k < n; k++)
        if (tree2[k] > min && tree2[k] < max)
            break;
    if (j == n && k == n) // 両方の配列で親要素が葉である場合
        return true;
    if (((j == n) ^ (k == n)) || tree1[j] != tree2[k])
        return false;
    return isSameCheckHelper(tree1, tree2, n, j + 1, k + 1, tree1[j], max) && // 右部分木のチェック
        isSameCheckHelper(tree1, tree2, n, j + 1, k + 1, min, tree1[j]); // 左部分木のチェック
}
bool areBSTSame(int first[], int second[], int n) {
    return isSameCheckHelper(first, second, n, 0, 0, INT_MIN, INT_MAX);
}
int main() {
    int first[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};
    int second[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};
    int n = sizeof(first) / sizeof(first[0]);
    if (areBSTSame(first, second, n)) {
        cout << "2つのBSTは同じです";
    } else {
        cout << "2つのBSTは同じではありません";
    }
}

実行結果

2つのBSTは同じです