题目：

输入一个整数数组，判断该数组是不是某个二叉搜索树的后序遍历的结果，如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

思路：

根据二叉搜索树的后序遍历特点，很容易可以判断该数组是否为后序遍历的结果。

在二叉搜索树的后序遍历序列中，最后一个数字是树的根节点的值，数组中前面的数字可以分为两部分，第一部分是左子树结点的值，他们都比根节点的值小；第二部分是右子树节点的值，他们都比根节点的值大。

因此，判断某数组是否为后序遍历的结果，可以先找到数组的最后一个数，即根节点的值，然后根据根节点的值找到第一部分（左子树，比根节点小），接着判断第二部分（右子树）的所有结点的值是否都比根节点的值大，如果不是，返回false。否则再判断第一部分和第二部分是否都为后序遍历结果（递归），如果是，则返回true。

类似题目：

将题目中的后序遍历改为先序遍历，思路一样。

代码：

#include 
     
      using namespace std;bool VerifySequenceOfBST(int sequence[],int length){    if(sequence==NULL || length<=0)        return false;    int root=sequence[length-1];    int leftIndex=0;    while(sequence[leftIndex]
      
       0)        left=VerifySequenceOfBST(sequence,leftIndex);    bool right=true;    if(leftIndex
      
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/a861533d45854474ac791d90e447bafd?rp=1

AC代码：

class Solution {public:    bool VerifySquenceOfBST(vector
     
       sequence) {        int length=sequence.size();        if(length<=0) return false;        return VerifySquence(sequence,0,length-1);    }        bool VerifySquence(vector
      
        sequence,int begin,int end) {        if(begin>=end)            return true;                int root=sequence[end];        int leftIndex=begin;        while(sequence[leftIndex]