剑指offer编程题—二叉搜索树的后序遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思考：
首先想到该题的考点之一：二叉搜索树的特性。
二叉搜索树又名二叉排序树，其或者是一棵空树，或者是具有下列性质的二叉树：
1）若它的左子树不为空，则左子树所有节点上的值均小于根节点的值；
2）若它的右子树不为空，则右子树所有节点上的值均大于根节点的值；
3）它的左右子树也都是二叉排序树；

解题思路1：若给定序列为某二叉搜索树的后序遍历序列，则该序列最后一个元素就是二叉搜索树的根节点。解题步骤如下：
1）找到root。给定序列的最后一个元素；
2）逆序遍历序列，找到第一个小于root的元素，则该元素左边（包括该元素）序列就是二叉搜索树左子树的后序遍历序列，元素右边（出去root）序列就是二叉搜索树右子树的后序遍历序列；
3）顺序遍历2）中找到的左子树的后序遍历序列，若发现大于root的元素，则返回false；
4）对2）中划分的左子序列和右子序列分别判断是否属于某二叉搜索树的后序遍历序列，即递归上述1-3步骤。

递归实现代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()<=0){
            return false;
        }
        else if(sequence.size()<3){
            return true;
        }
        int root=sequence[sequence.size()-1];
        int i=sequence.size()-2;
        while(sequence[i]>=root && i>=0){
            --i;
        }
        if(i>=0 && i<sequence.size()-2){
            int j=0;
            while(j<=i){
                if(sequence[j]>root){
                    return false;
                }
                ++j;
            }
            vector<int> left(sequence.begin(),sequence.begin()+i+1);
            vector<int> right(sequence.begin()+i+1,sequence.end()-1);
            return VerifySquenceOfBST(left)&&VerifySquenceOfBST(right);
        }
        else{
            vector<int> child(sequence.begin(),sequence.end()-1);
            return VerifySquenceOfBST(child);
        }
    }
};

非递归实现思路：
非递归也是基于递归的思想。左子树的所有节点的值都小于根节点的值，并且小于右子树所有节点的值。去掉根节点，剩余序列分为左右两部分，右子序列的最后一个数字就是右子树的根，也比左右子序列的所有数值大，遍历到达左子树时也把左子树当作右子树进行处理。
题解代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size = sequence.size();
        if(0==size)return false;
        int i = 0;
        while(--size)
        {
            while(sequence[i++]<sequence[size]);
            while(i<size && sequence[i++]>sequence[size]);
            if(i<size)return false;
            i=0;
        }
        return true;
    }
};