剑指Offer算法题-二叉搜索树的后序遍历序列

题目描述

输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题解

这道题用递归的思想比较容易理解，要知道，BST的左子树的所有节点一定比根节点小，右子树所有节点一定比根节点大，根节点在后序序列中的最后一项，通过找第一个比根节点数大的节点位置index，即可分离开左右子树。左子树是[start, index)，右子树是[index, end)。这时，需要判定右子树是否全部节点比根节点小，在下面的程序中，JudgeAndFindNext函数实现了判断。

这里要注意，当序列为空的时候，必须返回false。当序列只有一个数的时候，这算是一个BST。要特别注意[1,2,3,4,5]和[5,4,3,2,1]这种子树残缺的情况。

class Solution {
public:
    int JudgeAndFindNext(vector<int> & seq, int n, int start, int end){
        //在seq的[start, end)中找根节点的后继
        //并判断后继是否均大于根节点
        //如果是，返回后继下标，反之，返回-1 
        bool flag = false;
        int index = -1;
        for(int i = start; i < end; i++){
            if(seq[i] >= n){
                if(!flag){
                    flag = true;
                    index = i;
                }
            }else{
                if(flag) return -1;
                index = i;    //为了解决无右子树时产生的bug 
            }
        }
        return index;
    }

    bool VerifySquenceOfBST(vector<int> sequence, int start = 0, int end = -1) {
        if(end == -1){
            end = sequence.size();
            if(sequence.size() == 0) return false;    //空序列不是BST 
        }
        if(end - start <= 1) return true;    //序列只有一个数，是BST 
        int next = JudgeAndFindNext(sequence, sequence[end-1], start, end - 1);    //找后继 
        if(next == -1) return false;    //如果返回-1，说明右子树有比根节点小的，不是BST 
        return     VerifySquenceOfBST(sequence, start, next) && \
                VerifySquenceOfBST(sequence, next, end-1);    //递归判断左右子树 
    }
};