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

发布于 / 刷题 / Comments Off on 剑指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);    //递归判断左右子树 
    }
};

转载原创文章请注明,转载自: 斐斐のBlog » 剑指Offer算法题-二叉搜索树的后序遍历序列
评论已关闭