题目

  • 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
  • 如果是则返回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);

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