크기가 n인 주어진 배열이 C++에서 n 레벨의 BST를 나타낼 수 있는지 확인하십시오.

배열 A가 있고 배열이 n 레벨의 BST를 나타낼 수 있는지 여부를 확인해야 합니다. 레벨이 이므로 다음과 같은 방식으로 트리를 구성할 수 있습니다. 숫자가 k이고 k보다 큰 값은 오른쪽으로 이동하고 k보다 작은 값은 왼쪽으로 이동한다고 가정합니다. 두 개의 목록이 있다고 가정합니다. {50, 20, 9, 25, 10} 및 {50, 30, 20, 25, 10}

첫 번째는 유효하지 않지만 두 번째는 유효합니다.

이를 확인하기 위해 BST를 만들고 높이를 확인하거나 배열 기반 접근 방식을 사용할 수 있습니다. 배열 기반 접근 방식은 아래와 같습니다 -

• 왼쪽 하위 트리의 최대 한계를 표시하기 위해 max =무한대, 오른쪽 하위 트리의 최소 한계를 표시하기 위해 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