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

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

代码

class Solution {
    vector<int> seq;
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) {
            return false;
        }
        this->seq = sequence;
		return verify(0, sequence.size() - 1);
    }
    
    //二叉搜索树的后序遍历,序列中的最后一个元素就是根节点,从左往右比根节点小的就是左子树,剩下的就是右子树,也要比根节点的值要大，时间复杂度是o(nlogn)
    bool verify(int s, int e) {
        if (s >= e) {
            return true;
        }
        int m = s;
        while (seq[m] < seq[e]) {
            ++m;
        }
        int t = m;
        while (t < e && seq[t] > seq[e]) {
            ++t;
        }
        if (t < e) {
            return false;
        }
        return verify(s, m - 1) && verify(m, e - 1);
    }
};