サイズnの指定された配列がnレベルのBSTを表すことができるかどうかをC++で確認してください

配列Aがあり、配列がnレベルのBSTを表すことができるかどうかを確認する必要があります。レベルがであるため、次のようにツリーを構築できます。数値をkとすると、kより大きい値は右側に移動し、kより小さい値は左側に移動します。 {50、20、9、25、10}と{50、30、20、25、10}の2つのリストがあるとします。

最初のものは無効ですが、2番目のものは有効です。

これを確認するには、BSTを作成して高さを確認するか、配列ベースのアプローチを使用します。アレイベースのアプローチは以下のようなものです-

• 2つの変数max=infinityを使用して、左側のサブツリーの最大制限をマークし、min =負の無限大を使用して、右側のサブツリーの最小制限をマークします。
• arr[i]からarr[n– 1]の範囲内の各要素について、次の手順を繰り返します
  • arr [i]>arr[i-1]およびarr[i]>minおよびarr[i]
  • それ以外の場合、arr[i]>minおよびarr[i] を更新します。
  • これらのいずれも有効でない場合、要素は新しいレベルに挿入されるため、中断します

例

#include <iostream>
using namespace std;
bool canMakeBSTifHeightN(int arr[], int n) {
   int min = INT_MIN;
   int max = INT_MAX;
   for(int i = 1; i < n; i++){
      if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
         min = arr[i - 1];
      } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] <
      max) {
         max = arr[i - 1];
      } else {
         return true;
      }
   }
   return false;
}
int main() {
   int elements[] = {50, 30, 20, 25, 10};
   int n = sizeof(elements)/sizeof(elements[0]);
   if (canMakeBSTifHeightN(elements, n))
      cout << "We can make BST of height " << n;
   else
      cout << "We can not make BST of height " << n;
}

出力

We can make BST of height 5