判断一个数组是否是后序遍历

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

题解：
个人觉得这个题目不是很难，就是关于树的题目了解了更多以后就会更加孰能生巧。

1. 首先给出来一个题目，判断是否是规律可循，对于树类型的题目来说大多数都是递归，栈操作，对左右进行判断。
2. 在完成这个题目之前完成过由先序和中序来构造一个二叉树，都会对于数组进行分割的操作，这个题目也同样是对数组进行左右的分割判断。
3. 后序遍历的特点是对于给定的左右还是说对于最开始的都是数组的最后一个是根节点，若是正常的二叉搜索树时候，左边的都小于根节点，右边的都大于根节点。就可以对于最后一个节点来进行左右节点的判断这个时候，就需要有一个初始的递归函数模型：

   private boolean isBST(int low,int high,int [] num);

   数组还是那个数组，只不过就是对其进行了分割。
4. 什么时候进行错误的判断这是第一个需要考虑的地方，在考虑这个之前，我们需要先找出来左右的分割点：

   // 这里的high传进来 一定是 num的长度减一 不然会出现数组的越界。
   int temp= num[high];
   int k=0
   for(int i=0;i<high；i++){
   if(num[i]<=temp && num[i+1]>=temp)
   k=i;
   break;
   }

   表示的是找出分割的点。
5. 那么到底什么才是判断错误的情况呢？
   无非就是对于一个树的根来说 其左子树大于根节点，或者是右子树小于根节点，这个时候我们就会发现对于上面的判断进行分割的地方就会出现问题，我们只能对于一方左右进行判断，假定我们对于左边做假设会有大于根节点的存在，就需要认定右边的都是大于根节点的，然后找出分界点。这个时候，就需要把上面的判断情况做一个更改。

   int temp=num[high];
        for(int i=high-1;i>=0;i--){
            if(num[i]<temp){
                p=i;
                break;
            }
             }

   这个时候我们认定的是对于大于根的都是其右子树，若是出现了有不对的地方，在左边判断左子树的时候来判断错误即可。
   下面来进行错误的判断

   for(int j=low;j<p;j++){
            if(num[j]>num[high])
                return false;
        }

   表示在左子树中是否会有大于我们通过“右子树”（这里的右子树是我们假定的情况下）找出来的根节点。即可进行判断错误的工作的进行。
   下面贴出完整的代码：

public class Solution {
public boolean VerifySquenceOfBST(int [] num) {
int len=num.length;
if(len==0)
return false;
return isbst(0,len-1,num);
}
private boolean isbst(int low,int high,int [] num){
if(high<=low)
return true;
int p=0;
int temp=num[high];
for(int i=high-1;i>=0;i--){
if(num[i]<temp){
p=i;
break;
}
}
for(int j=low;j<p;j++){
if(num[j]>num[high])
return false;
}
return isbst(low,p,num)&&isbst(p+1,high-1,num);

}

}

总结： 可能是之前对于构建二叉树时候的思维定式，在进行根节点的判断考虑的是两边的情况（因为他们的序列是对的，所有可以这样操作，其实判断一边也都想），但是在后面的判错误时候依赖的又是一边的情况，所有就会导致错误的出现。觉得这里需要注意。其实这道题目也不失为一道考验对树理解的一道好题。