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

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

有点像通过前序和中序遍历重建二叉树

class Solution {
public:
    vector<int> nums;
    bool verifyPostorder(vector<int>& postorder) {
        nums=postorder;
        return dfs(0,nums.size()-1);
    }
    
    bool dfs(int l,int r){
        if(l>=r)return true;
        int root=r;
        // 右子树的根
        int r2=root-1;
        int r1=r2;
        // 左子树的根，已经按右子树的规则去找左子树的根
        while(r1>=0 && nums[r1]>nums[r])r1--;
        // 如果左子树中有比root大的值，则导致不合法
        for(int i=l;i<=r1;i++) {
            if(nums[i]>nums[r])
                return false;
        }
        
        if(!dfs(l,r1)) return false;
        if(!dfs(r1+1,r2)) return false;
        return true;
    }
        
};