题目

• 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
• 如果是则返回true，否则返回false。
• 假设输入的数组的任意两个数字都互不相同。
• 数据范围：

数组长度 [0,1000]。

示例

• 示例1

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

代码

解法：分治

class Solution {
public:
    vector<int> s;
    bool verifySequenceOfBST(vector<int> seq) {
        s = seq;    // 因为 dfs 里面会用到
        /*
            观察：[4, 8, 6, 12, 16, 14, 10] 。    [10] 无疑是根节点
            [4, 8, 6] 都比 10 小在左子树，[12, 16, 14]都比 10 大在右子树
        */
        // 空树为 true
        if(seq.empty()) return true;
        dfs(0,seq.size()-1);
    }
    
    bool dfs(int l,int r){
        // 截止条件
        if(l >= r)  return true;
        // 判断
        int k = 0;
        while(k < r && s[k] < s[r])   k++;    // 退出循环之后 s[k] 为右子树第一个元素
        for(int i = k; i < r; i++){
            if(s[i] < s[r])   return false;
        }
        return  dfs(l,k-1) && dfs(k,r-1);
    }
};

代码解析：1、在后序遍历序列 [4, 8, 6, 12, 16, 14, 10] 中， [10] 无疑是根节点。[4, 8, 6] 都比 10 小在左子树，[12, 16, 14]都比 10 大在右子树。
2、dfs(int l,int r) 中：

while(k < r && s[k] < s[r])   k++;

这一步为了得到左子树序列和右子树序列

3、这一递归调用要注意，不加 r，因为 r 是根节点，要判断的是左子树的合法性和右子树的合法性。

return  dfs(l,k-1) && dfs(k,r-1);

题目：二叉搜索树的后序遍历序列