《剑指Offer》二叉搜索树的后序遍历序列

从到，比递归效率更高的方法：上限约束法

方法一：递归法

递归简单易懂容易实现，先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：二叉搜索树不一定是棵平衡二叉树，因此其树形可能长得奇形怪状，最坏的情况下可能退化成一类似链表的结构，此时我们需要遍历n趟，每趟都需要遍历剩余未确定的元素，因此，递归方法的最坏复杂度是

方法二：上限约束法

那么贪婪的我们不禁就会想，有没有更好的方法？？O(n)、甚至O(logn)？

由于一个正确的遍历序列，我们可以在它任意一个位置故意篡改，因此势必要遍历所有的元素才能确定它的正确性，所以个人认为，这个问题的时间复杂度下界应该就是O(n)。

具体来说，二叉搜索树的关键特征是：对于任意一棵子树，均有“左子树<根节点<右子树”，因此，它的根节点约束了它左右子树的取值范围，二叉搜索树的根root是它左子树值的上限（max），同时是它右子树值的下限（min）。如果我们从根节点出发往下走，那么高层祖辈节点序列就会不停地对低层未遍历节点形成一个上下限约束，只要低层节点没有违背这个约束，那么它就是合法的，否则，序列就是不合法的。

因为后序遍历的一些特性，我们可以从右到左倒序访问给定的序列，因为后序遍历的最后一个元素是根节点，倒序访问就相当于是从根到叶，从右到左的访问顺序，从根到叶可以让我们利用祖辈节点提供的上下限约束信息来判断孩子节点合法性，具体步骤如下：

• 如果当前元素 > 上一个元素，这说明当前元素可能是上一个元素的右孩子，这时候：
• 如果当前元素突破max上限约束，说明祖辈中存在 “左子树 > 根” 的情况，违背了搜索树的定义（尝试把图中4的值换成7，那么就有子辈7 > 祖辈max约束5，搜索树不成立）；
• 否则，当前元素就是上一个元素的右孩子，当前元素将成为新的祖辈节点，为后续节点提供约束；
• 如果当前元素 < 上一个元素，这就说明当前元素是某个祖辈节点的左孩子，这时候：
• 我们需要找出这个祖辈节点，并将该祖辈的右子树节点全部丢弃（因为它的右子树结构已经确定，无法为后续节点提供帮助），该祖辈节点的值将成为新的max上限约束，
• 当前元素将成为新的祖辈节点，继续为后续节点提供约束；

因此，我们需要使用一个栈来存储已经确定了的祖辈节点，当新节点的合法性被确定时，入栈，当算法需要寻找当前节点是谁的左孩子时，出栈；

复杂度分析：由于后面贴出的代码使用了双重循环，所以可能让人迷惑，这里简单说明一下：内循环的执行总次数为pop的次数，而pop次数等于push次数(同一个节点不会反复入栈出栈)，显然，push次数为n次，因此内循环的总执行次数也为n次，故时间复杂度为O(n)，显然，空间复杂度也是O(n)。

特别说明：这个算法一开始使用了三个栈，比较繁琐，后来经过用户遗忘201901051244512的二次优化，变得更为简练，下面给出算法的动态示意图，节点为白色表示在栈中，变为灰色表示出栈：

下附代码，代码比较简单：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> &amp;seq) {
        if (seq.size() &lt; 1) return false;
        
        // roots栈里面依次存放各层祖辈节点的值
        // 事先放入一个值以避免对空栈进行判断
        stack<int> roots;
        roots.push(INT_MIN);
        int max = INT_MAX;
        for (int i=seq.size()-1; i &gt; -1; i--) {
            // 当节点超过max约束时，它必定不是二叉搜索树
            if (seq[i] &gt; max) return false;
            
            // 如果节点小于roots的栈顶，说明该节点是某个祖辈的左孩子
            // 不断出栈，直到找出该祖辈，同时，该祖辈也提供了新的max约束
            while (seq[i] &lt; roots.top()) {
                max = roots.top();
                roots.pop();
            }
            // 该节点成了新一代的祖辈节点，为后续节点判断自己的位置提供依据
            roots.push(seq[i]);
        }
        return true;
    }
};