Вот мой код, есть три тестовых примера, но я прошел только два из них. И я не понимаю, что не так с кодом. Пожалуйста, помогите мне!
#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
Inorder может гарантировать неубывающий заказ для BST, но плакатный заказ не может. И вы не можете вывести исходное двоичное дерево из последовательности постеров. Возьмем, например, 5 7 6 может быть действительным полный BST также может быть недействительным BST.