题解 | #二叉搜索树的后序遍历序列#

#include <cstddef>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0){
            return false;
        }
        return myVeriftySequenceOfBST(sequence,0, sequence.size()-1);
    }

    bool myVeriftySequenceOfBST(vector<int>& sequence, int l, int r){
        if(l>=r){
            return true;
        }
        int root_val = sequence[r];
        int i = r;
        int right_tree_count = 0;
        for(;i>=l;i--){
            if(sequence[i] < root_val){
                right_tree_count = r - i-1;
                // 同时需要保证左边所有元素都小于root_val;
                while(i>=l&& sequence[i]< root_val)
                {
                    i--;
                }
                if(i>=l){
                    return false;
                }
                break;
            }
        }
        return myVeriftySequenceOfBST(sequence,l, r - right_tree_count-1) && myVeriftySequenceOfBST(sequence, r-right_tree_count, r-1);
    }
};

同时需要保证左子树的所有元素都小于根节点元素。