大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
转载请注明出处：http://blog.csdn.net/ns_code/article/details/26092725
剑指offer上的第24题，主要考察递归思想，九度OJ上AC。
- 题目描写叙述：
-
输入一个整数数组，推断该数组是不是某二叉搜索树的后序遍历的结果。假设是则输出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
要紧紧抓住二叉搜索树的特点，对于后序遍历序列，其每一个子树的最后一个元素会比前面的左边一部分大，右边一部分小，这样便能够通过递归来推断。
AC代码例如以下：
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
bool IsBehSequenceBST(int *seq,int len)
{
if(seq==NULL || len<1)
return false;
int root = seq[len-1];
int i;
for(i=0;i<len-1;i++)
if(seq[i]>root)
break;
//第一个右子树元素的下标
int RightStart = i;
for(;i<len-1;i++)
if(seq[i]<root)
return false;
bool left = true;
if(RightStart > 0)
left = IsBehSequenceBST(seq,RightStart);
bool right = true;
if(RightStart < len-1-RightStart)
right = IsBehSequenceBST(seq+i,len-RightStart-1);
return (left && right);
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
int *seq = (int *)malloc(n*sizeof(int));
if(seq == NULL)
exit(EXIT_FAILURE);
int i;
for(i=0;i<n;i++)
scanf("%d",seq+i);
if(IsBehSequenceBST(seq,n))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
/**************************************************************
Problem: 1367
User: mmc_maodun
Language: C
Result: Accepted
Time:70 ms
Memory:1308 kb
****************************************************************/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118828.html原文链接：https://javaforall.net
