- 题目描述：
-
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 输入：
-
每个测试案例包括2行：
第一行为1个整数n(1<=n<=10000)，表示数组的长度。
第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。
- 输出：
-
对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。
- 样例输入：
-
7
5 7 6 9 11 10 8
4
7 4 6 5
- 样例输出：
-
Yes
No
- 代码：
#include <cstdio>
int isValid(int a[], int low, int high) {
if (low >= high)
return ;
int root = a[high];
int i = low;
while (a[i] < root && i <= high)
i++;
for (int j = i; j < high; j++)
if (a[j] < root)
return false;
return isValid(a, low, i - ) && isValid(a, i, high - );
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int a[n];
for (int i = ; i < n; ++i)
scanf("%d", &a[i]);
if (isValid(a, , n - )) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return ;
}
/**************************************************************
Problem: 1367
User: tonyhu
Language: C++
Result: Accepted
Time:10 ms
Memory:1020 kb
****************************************************************/