class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.empty())
            return true;
        return devide_and_rule(0,postorder.size()-1,postorder);	// 递归
    }
    bool devide_and_rule(int left,int right,vector<int>& postorder){
        if(left>=right)	// 只有一个节点
            return true;
        int root = postorder[right];	// 根是最后一个节点
        int i=right-1;
        while(i>=0 && postorder[i]>root)	// 从右向左找左子树
            i--;
        int mid = i;
        while(i>=0 && postorder[i]<root)	// 判断左子树中是否还存在比根大的值，若存在返回fause
            i--;
        if(i>=0)			// 正常是-1
            return false;
        return(devide_and_rule(left,mid,postorder)&&devide_and_rule(mid+1,right-1,postorder));	// 递归判断左子树和右子树
    }
};