二叉搜素树的后续遍历

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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<stdio.h>
#include<stdlib.h>

bool verifySquenceOfBST(int sequence[] ,int length)
{
	if(sequence==NULL||length<0)
		return false;
	
	//二叉搜索树的root是序列最后一个值 
	int root = sequence[length-1];
	
	//在二叉搜素树中左子树的节点小于根节点
	
	int i=0;
	
	for(;i<length-1;++i)
		if(sequence[i]>root)
			break;
	//在二叉搜素树中右子树的节点大于根节点
	
	int j=i;
	for(;j<length-1;++j)
		if(sequence[j]<root)
			return false;
			
	//判断左子树是不是二叉搜素树
	bool left=true;
	if(i>0)
		left=verifySquenceOfBST(sequence,i);
	 //判断右子树是不是二叉搜素树
	 
	 bool right=true;
	 
	 if(i<length-1)
	 	right=verifySquenceOfBST(sequence+i,length-i-1);
		
		
	return (left&&right); 
	 
} 

int main()
{
	int length;
	scanf("%d",&length);
	
	int sequence[length];
	int data;
	for(int i=0;i<length;i++)
		{
			scanf("%d",&sequence[i]);
			//scanf("%d",&data);
			//sequence[i]=data;
		}
		
	if(verifySquenceOfBST(sequence,length))
		printf("yes");
	else
		printf("no");
		
		return 0;
}

结果：