二叉搜索树的后序遍历序列

/*************************************************************
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历
的结果。如果是则返回true,否则返回false。假设输入的数组的任意两
个数字互不相同。
**************************************************************/

#include<stdio.h>
bool verifysequenceOfBST(int* sequence, int length)
{
	if(!sequence || length<=0)
		return false;

	
	int root = sequence[length-1];
	int i;

	for(i=0; i<length-1; ++i)
	{
		if(sequence[i]>root)
			break;
	}
	int j = i;
	for(;j<length-1; ++j)
	{
		if(sequence[j]<root)
			return false;
	}
	
	bool bLeft = true;
	if(i>0)
		bLeft = verifysequenceOfBST(sequence,i);

	bool bRight = true;
	if(i<length-1)
		bRight = verifysequenceOfBST(sequence+i,length-i-1);

	return (bLeft && bRight);
}
int main()
{
	int arr[7] = {5,7,6,9,11,10,8};
	if(verifysequenceOfBST(arr,7))
		printf("yes!\n");
	else
		printf("no！\n");
	return 0;
}

子序列，接下来在递归地处理这两个子序列。

==参考剑指OFFER

二叉搜索树的后序遍历序列,布布扣,bubuko.com

二叉搜索树的后序遍历序列

原文：http://blog.csdn.net/walkerkalr/article/details/21116729