[C++知识库]剑指33：二叉搜索树的后序遍历

错误方法：

class Solution {
public:
    vector<int> temp;
    bool verifyPostorder(vector<int>& postorder) {
        
        return posthelper(postorder,0,postorder.size()-1);

    }

    bool posthelper(vector<int>& postorder,int l,int r){
        if(l>=r)
            return true;
        int root=r;
        int length=r-l+1;
        int left=l+(length)/2-1;    //由于不是完全二叉树，比如只有一个子结点，就不对
        int right=r-1;
        if(postorder[left]<postorder[root] && postorder[right]>postorder[root])
            return posthelper(postorder,l,left) && posthelper(postorder,left+1,right); 
        else
            return false;
    }

};

正确解

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {    
        return posthelper(postorder,0,postorder.size()-1);
    }

    bool posthelper(vector<int>& postorder,int l,int r){
        if (l >= r) 
            return true;
        int i;
        for(i=r;i>=l;i--){    //搜索左子树最右边的结点
            if(postorder[i]<postorder[r])
                break;
        }
        for(int j=i;j>=l;j--){
            if(postorder[j]>postorder[r])
                return false;
        }
        return posthelper(postorder,l,i) && posthelper(postorder,i+1,r-1); 
    }

};