【剑指offer】_09二叉搜索树的后序遍历序列

题目描述

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

解题思路

比如下面的这棵二叉搜索树

它的后序遍历为0214369875；
我们设当前根节点为root;
第一次root=5
我们可以看出以3和6中间为分割线，左边为5的左子树，右边为5的右子树，数组最后一个数为5，为根结点。所以 {0,2,1,4,3}<root;{6,9,8,7}>root
size–1;
root = 7;
去掉5，最后一个数为7，它是以5为根结点的右子树，那么它肯定大于以5为根节点的左子树并且大于本身的左子树
{0,2,1,4,3}<root;{6}<root;{9,8}>root;
size–1;
root = 8;
当数据规模再减1时，则走到了根结点的右子树的右子树，那么此时的root，它肯定大于以5为根节点的左子树，和以7为根节点的左子树，和自身的左子树，小于自身的右子树
那么size–1一直持续下去，数组最后一个根节点永远都是上述的结论，就算到以5为根结点的左子树中也成立，所以再这个持续的过程中，一旦出现与上述结论相悖的情况，就说明此数不是二叉搜索树
如果最后size为0了，则说明此树为二叉所搜树。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size = sequence.size(); //求出数组长度
        if(0==size)                //为0返回
            return false;
        int i = 0;
        //去掉总根结点后，数组最后一个元素就是右子树的根结点，它的左子树都比它小，右子树都比它大
        //那么size再--，就到了右子树的右子树或者到左子树，上述条件仍然成立
       while(--size)
       {
            while(sequence[i++]<sequence[size]); //看左子树的值是不是都小于根结点
            while(sequence[i++]>sequence[size]); //右子树的值是不是都大于根结点
            
            if(i<size) //如果最后i还没有和size相同，返回错误
                return false;
           i = 0;
       }
        return true;
    }
};