递归

一棵二叉树是二叉搜索树（BST）的充分必要条件是：

• 它根节点的左子树是一棵BST；
• 它根节点的右子树是一棵BST；
• 它根节点的值大于左子树的最大值，小于右子树的最小值。

当前数组的尾部一定是二叉树的根节点，我们需要将当前数组除去尾部元素后的部分分为两段，划分规则就是上述的第三点：我们先找到右子树区间（可以为空）（右子树区间是按照规则找的，所以无需再次验证了），再去验证前面剩下的部分（可以为空）是否都小于根节点。然后再依次递归验证第一点和第二点。

class Solution {
    bool VerifyHelper(vector<int>& sequence, int l, int r) {
        if (l >= r) {
            return true;
        }

        int root = sequence[r - 1];
        int i = r - 2;
        while (sequence[i] >= root) {
            i--;
        }

        int j = i;
        for (; j >= l; --j) {
            if (sequence[j] >= root) {
                return false;
            }
        }

        return VerifyHelper(sequence, l, i + 1) &&
            VerifyHelper(sequence, i + 1, r - 1);
    }

public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) {
            return false;
        }
        return VerifyHelper(sequence, 0, sequence.size());
    }
};

单调栈

首先回顾一下前序、中序、后序遍历，这里借助一下CS61B的课件：

后序遍历的顺序实际上是逆时针经过每个节点的右侧的顺序，如果我们反着遍历数组，那么就是顺时针经过节点右侧的顺序。

在逆向遍历数组的过程中，我们维护一个递增的单调栈：

• 如果当前元素比栈顶大：我们正在向右侧走，入栈；
• 如果当前元素小于栈顶：我们进入了一个节点的左子树：
• 通过循环出栈比当前节点大的元素找到该节点；

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        // 处理序列为空情况
        if(sequence.size() == 0) return false;
        
        stack<int> s;
        int root = INT_MAX;
        // 以根，右子树，左子树顺序遍历
        for(int i = sequence.size() - 1; i >= 0; i--) {
            if(sequence[i] > root) return false;
            
            while(!s.empty() && sequence[i] < s.top()) {
                root = s.top();
                s.pop();
            }
            // 每个数字都要进一次栈
            s.push(sequence[i]);
        }
        return true;
    }
};