【正确答案】基本设计思想：首先，使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。 以数组{5，7，6，9，11，10，8}为例，后序遍历结果的最后一个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的根结点的左子树特点；后3个数字9、11和10都比8大，是值为8的根结点的右子树结点。接下来需要用同样的方法确定与数组每一部分对应的子树结构。很明显，这是一个递归的过程。对于整数序列5、7和6，最后一个数字6是左子树的根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11和10中，最后一个数字10是右子树的根结点的值，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。 再举一个反例。例如整数数组{8，1，6，5}，后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字8大于5，因此可以肯定此二叉排序树的根结点上没有左子树，数字8、1和6都是右子树结点的值。但发现在右子树中有一个结点的值是1，比根结点的值5小，这就违背了二叉排序树的定义。因此，不存在一棵二叉排序树，它的后序遍历的结果是8、1、6、5。 以上分析足以看出规律所在。接下来写代码吧!

【正确答案】算法实现如下： bool verifySquenceOfBST(int squence[],int length) { //判断非法输入数组 if(squence==NULL||length＜=0) return false; //将数组的最后一个值赋值给根结点的值 int root=squence[length-1]; //在二叉排序树中左予树的结点值小于根结点的值 int i=0; for(;i＜length-1;i++) { if(squence[i]＞root) break; } //在二叉排序树中右子树的结点值大于根结点的值 int j=i; for(;j＜length-1;j++) { if(squence[j]＜root) return false; } //判断左子树是不是二叉排序树 bool left=true; if(i＞0) left=verifySquenceOfBST(squence,i); //判断右子树是不是二叉排序树 bool right=true; if(i＜length-1) right=verifySquenceOfBST(squence+i,length-i-1); return(left && right); }

【正确答案】算法每次确定当前数组中的最后一个为子树的根，然后对数组进行扫描，把数组分成两部分，前面一部分是比根小的，作为左子树，后面一部分比根大的，作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树，并判断构造出来的树是否合法。同样地考虑一个递增的数组，每次只能分离出最后一个作为树根，然后往下递归。在这个过程中，第i层的数组里有n-i+1个数，这样总的扫描的次数为n(n-1)/2，所以时间复杂度为O(n²)。