讨论/《图解算法数据结构》 - 剑指 Offer 33. 二叉搜索树的后序遍历序列/
《图解算法数据结构》 - 剑指 Offer 33. 二叉搜索树的后序遍历序列

跟方法一思路一样但不知道哪错了......

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

1
展开全部 9 讨论