确定数组是否是遍历二叉搜索树的结果（思想和实现）

以下是与二叉搜索树的后遍历序列有关的示例，包括思想和代码实现.

标题:

输入一个非空整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出是，否则，则输出否.

假设输入数组中的任何两个数字都不相同.

想法1:

BST的后序列的合法序列是序列S的最后一个元素是x（即根）. 如果删除最后一个元素的顺序为T，则T满足: T可分为2个部分，在一个部分（左子树）小于x二叉排序树 遍历，下一个部分（右子树）大于x之前，这两个部分部分（子树）都是合法序列序列. 递归的完美定义: ））.

代码实现:

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;
    }
};

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-246383-1.html