题目描述

此题的重点是考察后序遍历的操作，左右根，也就是将最后一个节点作为分割元素，将分割为左子树、右子树和根节点，再递归判断左右子树是否满足后序遍历的特性，不满足则返回false。递归出口有两个，一个是当序列的左侧位置大于等于右侧位置是返回true，解释下此处为什么会存在大于的情况，以左子树为例，可能会存在某一点没有左子树，而我们对左子树的区间判断是s到l-1，此处的l就是s。每次递归都会干掉最后一个元素。

算法1

(dfs) $O(n)$

C++ 代码

class Solution {
public:
    bool verifySequenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0) return true;
        return dfs(sequence, 0, sequence.size() - 1);
    }
    bool dfs(vector<int>& sequence, int s, int e)
    {
        if(s >= e) return true;
        int root = sequence[e];
        int l = s;
        while(sequence[l] < root) l++;
        for(int i = l; i < e; i ++ )
        {
            if(root > sequence[i]) return false;
        }
        return dfs(sequence, s, l - 1) && dfs(sequence, l, e - 1);
    }
};