题目描述

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

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

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

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

算法1

(暴力枚举) $O(n^2$

C++ 代码

 //二叉搜索树， 最后一个元素一定是根节点，可以从左向右遍历，
 //找到第一个大于根节点值的数。这个数就是 右子树的第一个点，然后递归处理。
 //还需要判断一下，在右子树区间里边，是不是每个元素都大于10，如果不是，则不是合法二叉搜索树

class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        int n = seq.size();
        if(n == 0) return true;
        return dfs( 0, n - 1);
        // return false;
    }

    bool dfs(int l, int r){
        if(l >= r) return true;
        //先找到根节点
        int root = seq[r];
        //找到第一个大于根节点值的数。即右子树第一个点
        int  k = l;
        while(k < r && seq[k] < seq[r]) ++k;
        //判断右边的子树是不是合法
        for(int i = k; i < r; ++i){
            if(seq[i] < seq[r]) return false;
        }
        return dfs( l, k - 1) && dfs(k, r - 1);
    }
};