判断给定序列是否为BST后序遍历序列

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

目录

一、BST

1.1 定义

1.2 性质

二、思路

2.1 非递归版本

2.2 递归版本

一、BST

1.1 定义

BST（Binary Search Tree）二叉搜索树：

1. 所有非叶子结点至多有两个孩子（二叉搜索树也属于二叉树的范畴）；
2. 所有结点只存储一个关键字；
3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；并且左右子树也是BST。（如果出现等于的情况，放在左子树部分和放在右子树部分，不影响）。

1.2 性质

1. 搜索时，从根结点开始，如果查询的关键字与根结点的关键字相等，那么就命中；如果查询的关键字比结点关键字小，就进入左子树部分进行查找；否则就需要进入右子树部分进行查找。查找到最后也没能找到，则报告找不到相应的关键字。
2. 如果BST的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么BST的搜索性能逼近二分查找，近似等于树高（logn）；但和连续空间的二分查找相比，优点是：改变BST结构（插入或删除操作）不需要移动大段的内存数据。
3. 对BST树进行中序遍历，将会得到非递减的序列。

二、思路

后序遍历BST得到的序列的性质是——最后一个元素x是根结点，以x为基准可将该序列（去掉x本身）划分成两个子序列，前一个子序列（左子树）所有元素值均小于x；后一个子序列（右子树）的所有元素值均大于x。前一个序列和后一个序列仍然满足该性质。这是一个典型的递归求解的问题！

分治法思想：字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题······直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

2.1 非递归版本

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        int i = -1;
        while(n > 1)    //只有1个结点的树也是BST。
        { 
            //第一个循环体结束时，i指向右子树序列开始位置；如果不存在右子树——会指向根结点。
            while(sequence[++i] < sequence[n-1]);  
            
            //警惕数组下标越界，第二个循环体正常结束，i将指向根结点的位置
            while(i < n-1 && sequence[i++] > sequence[n-1]);
            if(i < n-1) return false;
            i = 0;
            n--;
        }
        return n == 0 ? false : true;
    }
};

2.2 递归版本

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(0 == n) return false;
        return judge_impl(sequence, 0, n-1);
    }
private:
    bool judge_impl(vector<int>& seq, int start, int end)
    {
        //start为序列的起始下标，end为序列中根结点的下标（最后一个元素）
        if(start >= end) return true;    //只有一个结点的序列肯定符合条件
        int i = start-1, j;
        while(seq[++i] < seq[end]);    //循环结束时i指向元素值不小于最后一个元素的位置
        for(j = i; j < end-1 && seq[j] > seq[end]; ++j);
        if(j < end-1) return false;
        return judge_impl(seq, start, i-1) && judge_impl(seq, i, end-1);
    }
};