题目:

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

思路：

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。

代码如下：

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