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

递归与非递归

递归

后续遍历最后一位肯定是中间值，根据这个值把数组划为两半，左边肯定是左子树，都得小于中间值，右边是右子树，都得大于中间值。然后看左右字数各自也得满足上述规律。因为分割后左右子树为空也是满足条件的，但是题目说空的不是搜索树，所以要单独再写一个回溯函数。
使用下标作为传递的参数可以减少vector的添加操作，节省时间（下方未使用）
使用一个成员变量来存数组配合传参下标可以进一步节省内存（下方未使用）

class Solution {
public:
    //bool backtra()
    bool backtra(vector<int> sequence) {
        if(sequence.size()<=1) return true;
        int root=sequence.back();
        vector<int> left;
        vector<int> right;
        int i=0;
        for(;i<sequence.size()-1&&sequence[i]<root;i++){
            left.push_back(sequence[i]);
        }
        for(;i<sequence.size()-1;i++){
            if(sequence[i]<=root) return false;
            right.push_back(sequence[i]);
        }
        return backtra(left)&&backtra(right);
    }
    bool VerifySquenceOfBST(vector<int> sequence){
        if(sequence.size()==0) return false;
        if(sequence.size()==1) return true;
        return backtra(sequence);
    }
};

非递归法

这个方法在评论区看的，但是直接用那个有点小问题

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size = sequence.size();
        if(0==size)return false;

        int i = 0;
        while(--size){
            while(sequence[i]<sequence[size]) i++;
            while(sequence[i]>sequence[size]) i++;
            if(i<size)return false;
            i=0;
        }

        return true;
    }
};

解释：最后一个是中间值，但是我们去掉最后一个，新的最后一个同样也满足我们说的规律！很有意思~所以就不需要递归，直接while就好了