总结【剑指Offer】二叉搜索树的后序遍历序列

一、递归法

1.分析：一次遍历确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。
2.代码

    bool IsBST(const vector<int>& sequence, const int start, const int end){
        if (start>=end) return true;  // 可能出现start>end的情况

        int pivot;
        for (pivot=start; sequence[pivot]<sequence[end]; ++pivot);  // 查找分界点
        for (int i=pivot; i<=end; ++i)
            if (sequence[i]<sequence[end]) return false;
        return IsBST(sequence, start, pivot-1) && IsBST(sequence, pivot, end-1);
    }

    bool VerifySquenceOfBST_1(vector<int> sequence) {
        if (!sequence.size()) return false;
        return IsBST(sequence, 0, sequence.size()-1);
    }

3.复杂度
时间复杂度：O(n*lgn)
空间复杂度：O(lgn)

二、直接法

1.分析：BST的中序遍历是有序的，所以将后序序列排序后可以得到BST的中序遍历序列，然后看这两个序列是否可以构建一颗二叉树
2.代码

    bool BuildTree(const vector<int>& in, const vector<int>& post){
        if (in.size()!=post.size()) return false;  // 非法情况，提前退出
        if (in.size()==0 || in.size()==1 && in[0]==post[0]) return true; // 递归出口
        // 在中序序列中查找root位置，确定左右子树位置
        vector<int>::const_iterator pos_in=find(in.begin(), in.end(), post.back());
        if (pos_in==in.end()) return false;
        int i=pos_in-in.begin(), j=in.end()-pos_in;

        vector<int> left_in(in.begin(), pos_in), left_post(post.begin(), post.begin()+i);
        vector<int> right_in(pos_in+1, in.end()), right_post(post.begin()+i, post.end()-1);
        return BuildTree(left_in, left_post) && BuildTree(right_in, right_post);
    }

    bool VerifySquenceOfBST_2(vector<int> sequence) {
        if (!sequence.size()) return false;
        vector<int> inOrder(sequence.begin(), sequence.end());
        sort(inOrder.begin(), inOrder.end());  // 构建辅助中序序列
        return BuildTree(inOrder, sequence);
    }

3.复杂度
时间复杂度：O(2n*lgn)
空间复杂度：O(n)

三、上下界约束法

1.分析：BST的特征是左<根<右（这个特点确定唯一的中序序列），后序遍历的顺序是左右根，基于此，当从后向前遍历后序序列时， 先遍历到根，然后遍历到大于根的结点则向右（并把未向左的结点压入栈中），最后遇到小于根的结点则向左（之后序列中的结点值不能大于此结点）。
2.代码

    bool VerifySquenceOfBST(vector<int> sequence) {
        if (!sequence.size()) return false;
        stack<int> min;
        int max=0x7fffffff;
        min.push(sequence.back());

        for (int i=sequence.size()-1; i>=0; --i){
            if (sequence[i]>max) return false;
            if (min.empty() || sequence[i]>min.top()) min.push(sequence[i]); //向右
            while (!min.empty() && sequence[i]<min.top()) {
                max = min.top();
                min.pop();
            } // 退栈，向左
        }
        return true;
    }

3.复杂度
时间复杂度：O(n)
空间复杂度：O(n)