题解 | #二叉搜索树的后序遍历序列#

单调栈似懂非懂，需要多理解一下

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
      //  单调栈
      if (sequence.empty()) {
        return false;
      }
      
      std::stack<int> s;
      int root = INT_MAX;
      
      //  从根左右遍历，所以使用逆序遍历
      for (int i = sequence.size(); i >= 0; --i) {
        //  根在根节点和右子树之前都是保持最大值
        if (sequence[i] > root) {
          return false;
        }
        //  确定根
        //  根在遍历到左子树的第一个节点时才发生改变
        while (!s.empty() && s.top() > sequence[i]) {
          root = s.top();
          s.pop();
        }
        s.push(sequence[i]);
      }
      
      return true;
    }
};

class Solution {
  public:
    bool VerifySquenceOfBST(vector<int> sequence) {
      if (sequence.empty()) {
        return false;
      }
      
      return curision(sequence, 0, sequence.size() - 1);
    }
  private:
    bool curision(const std::vector<int> &sequence, int l, int r) {
      //  遍历到只剩下一个节点
      if (l >= r) {
        return true;
      }
      //  当前子树的根
      int mid = sequence[r];
      int j = r;
      //  寻找左子树第一个节点
      //  寻找的过程中已经过滤出右子树全部比根大
      for (; j >= 0; --j) {
        if (sequence[j] < mid) {
          break;
        }
      }
      //  判断左子树是否满足全部比根小
      for (int i = j; i >= 0; --i) {
        if (sequence[i] > mid) {
          return false;
        }
      }
      //  递归细分到每一颗子树
      return curision(sequence, l, j) && curision(sequence, j + 1, r - 1);
    }
};