下面要给大家分享的是和二叉搜索树的后序遍历序列相关的实例，具体包括了思路和代码实现。

题目：

输入一个非空整数数组，判断这个数组是否为某二叉搜索树的后序遍历的结果。假如是的话，那么输出Yes,假如不是的话，那么输出No。

假设输入的数组的任意2个数字都是不同的。

思路1：

BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x (也就是根)，假如去掉最后一个元素的序列为T，那么T满足：T可以分成2段，前一段(左子树)小于x，后一段(右子树)大于x，且这2段(子树)都是合法的后序序列。完美的递归定义 : ) 。

代码实现：

class Solution {
    bool judge(vector
<int>& a, int l, int r){
        if(l >= r) return true;
        int i = r;
        while(i > l && a[i - 1] > a[r]) --i;
        for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false;
        return judge(a, l, i - 1) && (judge(a, i, r - 1));
    }
public:
    bool VerifySquenceOfBST(vector
    <int> a) {
        if(!a.size()) return false;
        return judge(a, 0, a.size() - 1);
    }
};

思路2

代码实现：

/*
//递归
class Solution {
public:
    bool VerifySquenceOfBST(vector
<int> sequence) {
 
        int size = sequence.size();
        if(0==size)
        {
            return false;
        }
 
        return isLastOrder(sequence, 0, size-1);
    }
 
private:
    bool isLastOrder(vector
    <int>& sequece, int b, int e)
    {
        if(b==e)
        {
            return true;
        }
        int mid = b;
        while(sequece[mid++]
        <sequece[e] && mid<e);
 
        int tmp = mid;
        while (sequece[tmp++]>sequece[e] && tmp
            <e);
        if(tmp
                <e)
        {
            return false;
        }
 
        if(mid==b || mid==e)
        {
            return isLastOrder(sequece, b, e-1);
        }
        else
        {
            return (isLastOrder(sequece, b, mid-1) && isLastOrder(sequece, mid, e-1));
        }
    }
};*/
 
//非递归 
//非递归也是一个基于递归的思想：
//左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的
//最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看有子树是否符合条件
//即可，即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理
 
//对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
//只需看看右子树的右子树是否符合要求即可
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]);
            while(sequence[i++]>sequence[size]);
 
            if(i
                        <size)return false;
            i=0;
        }
        return true;
    }
};

思路3：

已知条件：

后序序列最后一个值为root，二叉搜索树左子树值都比root小，右子树值都比root大。

一、确定root;

二、遍历序列(除去root结点)，找到第一个大于root的位置，则该位置左边为左子树，右边为右子树;

三、遍历右子树，假如发现有小于root的值，那么就直接返回false;

四、分别判断左子树和右子树是否仍是二叉搜索树(即递归步骤1、2、3)。

代码实现：

class Solution {
public:
    bool VerifySquenceOfBST(vector
<int> sequence) {
        vector
    <int> leftTree,rightTree;
        int root; // 根结点
        if(sequence.empty()) return false;
        int index = 0; // 标记左右子树界限
        int len = sequence.size();
        root = sequence[len-1];
        int i=0;
        for(;i<len-1;++i)
        {
            if(sequence[i]>root) break; // 找到第一个大于根结点的位置，则左边为左子树，右边为右子树
        }
        for(int j=i;j
        <len-1;++j) // 循环时去除root，因此为len-1
        {
            if(sequence[j]
            <root) return false; // 有一个小于root，则返回false
        }
         
        if(i!=0)
        {
            // 即有左子树
            for(int m=0;m
                <i;++m)
            {
                leftTree.push_back(sequence[m]);
            }
        }
        if(i!=len-2)
        {
            for(int j=i;j
                    <len-1;++j)
            {
                rightTree.push_back(sequence[j]);
            }
        }
         
        bool left = true,right = true; // 看左右子树是否是二叉搜索树
        if(leftTree.size()>1) VerifySquenceOfBST(leftTree);
        if(rightTree.size()>1) VerifySquenceOfBST(rightTree);
         
        return (left&&right);
    }
};

以上的三种思路和代码实现大家都了解了吗?想了解更多java实例，请继续来奇Q工具网的java实例专栏了解吧!