Оцените, действителен ли порядок постов двоичного дерева поиска

Вот мой код, есть три тестовых примера, но я прошел только два из них. И я не понимаю, что не так с кодом. Пожалуйста, помогите мне!

#include <cstdio>

int isValid(int a[], int low, int high) {
if (low >= high)
return 1;

int root = a[high];
int i = 0;
while (a[i] < root && i < high)
i++;
// i == low, the left child is null
// i == high, the right child is null
if (a[i - 1] < root && root < a[high - 1]
|| i == low && root < a[high - 1] || a[i - 1] < root && i == high) {
return isValid(a, low, i - 1) && isValid(a, i, high - 1);
} else {
return 0;
}
}

int main() {
int n;
while (scanf("%d", &n) != EOF) {
int a[n];
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);

if (isValid(a, 0, n - 1)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}

Пример ввода:

7

5 7 6 9 11 10 8

4

7 4 6 5

Образец вывода:

Yes

No

0

Решение

Inorder может гарантировать неубывающий заказ для BST, но плакатный заказ не может. И вы не можете вывести исходное двоичное дерево из последовательности постеров. Возьмем, например, 5 7 6 может быть действительным полный BST также может быть недействительным BST.

0

Другие решения


По вопросам рекламы [email protected]