C++でツリーを構築せずに同一のBSTを確認する

BSTの要素を表す2つの配列があります。その配列から要素を左から右に取得してBSTを形成する場合、両方の配列から取得することで、同じBSTを作成します。両方が同じように形成されているかどうかを確認する必要があります。しかし、制約は、BSTを作成できないことです。 2つの配列が{2、4、1、3}と{2、1、4、3}であるとすると、これらのシーケンスは両方とも同じBSTを形成できます。

アプローチは簡単です。ご存知のように、左側のサブツリーの要素はルートよりも小さく、右側のサブツリーの要素はルートよりも大きくなっています。これらの2つのリストは、各要素xについて、xの左右のサブツリーの要素が両方の配列の後ろに表示される場合に同じBSTを表すことができます。左右のサブツリーのルートについても同じことが言えます。次に小さい要素と大きい要素が両方の配列で同じであるかどうかを確認します。この同じプロパティは、左右のサブツリーに対して再帰的にチェックされます。

例

#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) //If the parent element is leaf in both arrays
      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) &&
   // for Right Subtree
   isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]); // for Left Subtree
}
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 << "Two BSTs are same";
   } else {
      cout << "Two BSTs are not same";
   }
}

出力

Two BSTs are same