转载请注明出处：

    剑指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
     
      #include
      
       #include
       
        bool IsBehSequenceBST(int *seq,int len){	if(seq==NULL || len<1)		return false;	int root = seq[len-1];	int i;	for(i=0;i
        
         root)			break;	//第一个右子树元素的下标	int RightStart = i;	for(;i
         
           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
         
        
       
      
     

/**************************************************************

    

Problem: 1367

    

User: mmc_maodun

    

Language: C

    

Result: Accepted

    

Time:70 ms

    

Memory:1308 kb

****************************************************************/