[AcWing]46. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

数据范围

数组长度 [0,1000]。

样例

1
2
3

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

算法思想

初始划分阶段：

数组最后一个元素一定是根元素，然后从左往右找到第一个比根元素大的下标，记为k。
左区间就是[0, k - 1]，右区间是[k, n - 1]。（n为数组长度)
然后对子区间做同样的划分。

注意事项：

区间长度为1，则后续遍历序列合法。
只有包含k的右区间可能会出现小于根节点的情况，因为左边已经在找k的过程中排除了非法情况（左区间中有比根节点大的元素）。

代码实现

class Solution {
public:

    bool dfs(int l, int r, vector<int> & seq){
        // 如果区间长度小于等于1，说明一切合法
        if(l >= r) return true;
        
        // 找到根节点
        int root = seq[r];
        
        // 从左往右找到第一个比根大的元素下标
        int k = l;
        while(k < r && seq[k] < root) k++;
  
        // 如果右区间有比根元素小的元素，一定不合法
        for(int i = k; i < r; i++)
            if(seq[i] < root)
                return false;
        
        // 左区间和右区间同时划分
        return dfs(l, k - 1, seq) && dfs(k, r - 1, seq);
    }

    bool verifySequenceOfBST(vector<int> sequence) {
        // 整个区间长度[0, n - 1]。
        return dfs(0, sequence.size() - 1, sequence);
    }
};