【原】每日一题 剑指offer（二叉搜索树的后序遍历序列）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

二叉搜索树的后序遍历序列

题目描述

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

解析

左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看有子树是否符合条件即可，即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理，对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树，只需看看右子树的右子树是否符合要求即可。

代码

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(sequence[i++]>sequence[size]);
           if(i<size)return false;
           i=0;
       }
       return true;
   }
};