http://www.acmerblog.com/offer12-2969.html
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
对应二叉树的问题普遍是用递归解决。二叉搜索树也就是二分查找树。左子树的每个节点都比根节点小，右子树的每个节点都比根节点大。
以 5 7 6 9 11 10 8 为例： 根节点为8，左子树为 5 7 6 又子树为 11 10。
所以，任务就是先找到左子树。
程序中是这样找的：
int k = start; //k为右子树的开始位置(左子树都是比根节点小的数)
while(arr[k] < arr[end] && k <= end-1) k++;
此时，arr[k] == 11。即右子树开始的位置。 接下来判断右子树是否是符合要求的，即都比根节点大。
http://bylijinnan.iteye.com/blog/1300758
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
对应二叉树的问题普遍是用递归解决。二叉搜索树也就是二分查找树。左子树的每个节点都比根节点小，右子树的每个节点都比根节点大。
以 5 7 6 9 11 10 8 为例： 根节点为8，左子树为 5 7 6 又子树为 11 10。
所以，任务就是先找到左子树。
程序中是这样找的：
int k = start; //k为右子树的开始位置(左子树都是比根节点小的数)
while(arr[k] < arr[end] && k <= end-1) k++;
此时，arr[k] == 11。即右子树开始的位置。 接下来判断右子树是否是符合要求的，即都比根节点大。
09 | int n, arr[10001], j; |
10 | bool check(int start, int end){ |
11 | //任意3个或3个以下的数都符合 |
12 | if(start >= end-2) return true; |
13 | int k = start; //k为右子树的开始位置(左子树都是比根节点小的数) |
14 | while(arr[k] < arr[end] && k <= end-1) k++; |
15 | j = k; |
16 | //只要右子树中有比根节点小的就不符合 |
17 | while(j < end) if(arr[j++] < arr[end]) return false; |
18 | return check(start,k-1) && check(k,end-1); //分别判断左右子树 |
19 | } |
20 | int main() { |
21 | while(scanf("%d", &n) != EOF){ |
22 | for(int i=0; i<n; i++) scanf("%d", &arr[i]); |
23 | if( check(0,n-1) ) puts("Yes"); |
24 | else puts("No"); |
25 | } |
26 | return 0; |
27 | } |
