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

题意：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

题解：二叉搜索树是，左子树上的节点都都小于根结点，右子树上的节点大于根结点，它的子树也满足这个规则。

后序遍历是左右根遍历。因此我们只需要判断，当前节点如果是在右子树上，那么必然不会再出现比他大的节点了。

代码：

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         if(sequence.empty())    return false;
 5         int len = sequence.size();
 6         int root = sequence[len-1];//后序数组里最后一个数是根节点
 7         
 8         bool flag = false;
 9         for(int i = 0; i < len-1 ;i++){
10             if(sequence[i] > root)    flag = true;    //当前已经是右子树节点
11             else{
12                 if(flag)    return false;    //此时在左子树，且已经搜索过右子树
13             }
14         }
15         
16         return true;
17     }
18 };