题目描述

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

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

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

样例

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

输出：true

dfs

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

后序遍历：遍历顺序为 根节点->左子树->右子树;
由这一性质可知，序列中最后一个值即为根节点的值，则只需要进行如下几步：
1. 获取根节点值
2. 确定左子树区间
3. 检测右子树区间是否存在比根节点小的值
4. 递归检测左、右子树是否为平衡二叉树

nlogn

参考文献

C++ 代码

class Solution {
public:
    // 避免多次参数传递
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(0, seq.size() - 1);
    }

    // dfs实现
    bool dfs(int l, int r){
        // 当子树为空树或者只有一个元素，则一定是二叉搜索树
        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)&&dfs(k, r - 1);
    }
};