0 引言

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 二叉搜索树的概念：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 二叉搜索树的基本性质：中序遍历非严格单调递增

1 抽象问题具体化

举例1：判断序列{2，1，3，5，7，8，6，4}是否是二叉搜索树的后序遍历序列.

1）4是根结点，以根结点为基准，将序列二分，左子树为从左到右直到某个数大于4为止；右子树为从该数到倒数第二个数为止，

同时对这其中的每个数进行判断，必须每个数都大于4才可以，对当前树的有效性作出判断。

2）对子树作同样的划分，划分的基准变为每个子树序列的最后一个结点，左子树为3，右子树为6。

3）结束的条件是划分到的子树为空。

判断结论为true.

 

2 具体问题抽象分析

 采用递归的方式逐级进行判断。

1）判断序列是否为空，空的话返回true.

2）以序列的最后一个结点为基准对序列进行划分，从左到右小于等于基准的数入左子树后序遍历序列，其他数入右子树后序遍历序列，将其他数入队时判断其是否大于基准数，如果存在不大于基准数的情况，返回false.

3)  左子树后序遍历序列递归，如果未返回false，右子树后序遍历序列递归，得到返回值.

4）return bool.

3 demo

bool VerifySquenceOfBST(vector
     
       sequence) {        if(sequence.empty())            return false;          int base = sequence[sequence.size()-1];        vector
      
        leftSequence;        vector
       
         rightSequence;        int position = -1;        for(int i=0;i
       
      
     

4 代码优化

判断语句太多，后边看看能不能合并一些，简化一下，里边肯定有冗余的判断。