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

给定一个序列，判断是不是一个二叉搜索树的后序遍历序列

思路：由后序遍历的特点我们知道，数组最后一个数字是根节点，前面的序列是其左右子树。从头开始查找第一个比根节点大的位置，就是右子树的根节点，它也是左右子树序列的分界点。应当满足从分界点往后一直到倒数第二个数值都比最后一个(根节点)大。反复迭代。

顺序流程.png

bool VerifyHelper(vector<int> seq, int start, int len)
{
    int root = seq[len-1];
    int i = 0;

    for(; i<len-1; ++i)
      if(seq[i] > root)
        break; // 找到分界点

      int j = i;
      for(; j<len-1; ++j)
        {
          if(seq[j] < root)
            return false; // 右子树比root小，不是后序
        }
      // 检查左右子树
      bool left = true;
      if(i > 0)
        left = VerifyHelper(seq, start, i);

      bool right = true;
      if(i<len-1)
        right = VerifyHelper(seq, i, len-1);

      return left&right;
}
bool VerifyPostOrder(vector<int> sequence)
{
    if(sequence.size() == 0)
       return false;
    int len = sequence.size();
    return VerifyHelper(sequence, 0 , len);
}