剑指 Offer 33. 二叉搜索树的后序遍历序列

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

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int n=postorder.size();
        if(n==0||n==1) return true;
        int root=postorder[n-1];
      //  cout<<root<<endl;
        int i;
        for(i=0;i<n-1;i++)
        {
            if(postorder[i]>root) break;
        }
        int temp=i;
        vector<int> left(postorder.begin(),postorder.begin()+i);
        for(;i<n-1;i++)
        {
            if(postorder[i]<root) break;
        }
        vector<int> right(postorder.begin()+temp,postorder.end()-1);
//cout<<i<<endl;
        if(i!=n-1) return false;
        else
        {
            return verifyPostorder(left)&&verifyPostorder(right);
        }
        


    }


};

这题的思路和中序+前序生成二叉树类似，同样也是划分为左右子树然后递归的思想。
但是没有一次过，细节上还是出了bug。
DEBUG日志：

首先我用的循环变量i在构建右子树的时候已经改变了，所以要在之前用temp记录。
（后来想到，我直接在第一遍把左右子树同时建立不就好了么…）
每个序列的最后一位是根，子序列不需要包含了所以右子树是右边边界是postorder.end()-1
返回值：序列为空或者只有一个值都返回True，不用下一步判断了。

优化一下：

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int n=postorder.size();
        if(n==0||n==1) return true;
        int root=postorder[n-1];
        int i;
        for(i=0;i<n-1;i++)
        {
            if(postorder[i]>root) break;
        }
        vector<int> left(postorder.begin(),postorder.begin()+i);
        vector<int> right(postorder.begin()+i,postorder.end()-1);
        for(;i<n-1;i++)
        {
            if(postorder[i]<root) break;
        }
        
        if(i!=n-1) return false;
        else
        {
            return verifyPostorder(left)&&verifyPostorder(right);
        }
        


    }


};