转载请注明出处：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;

}