题目难度：中等

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。数据范围：节点数量 $0 \leq n \leq 1000 0≤n≤1000$ ，节点上的值满足 $1 \leq v a l \leq 1 0^{5} 1≤val≤10^5$ ，保证节点上的值各不相同要求：空间复杂度 $O (n)$ ，时间时间复杂度 $O (n^{2})$ 提示： 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历 4.参考下面的二叉搜索树，示例 1 JZ-33

示例1:

输入：[1,3,2] 返回值：true 说明：是上图的后序遍历，返回true

二叉搜索树（Binary Search Tree,BST）/ 二叉排序树

思路1：单调栈

时间复杂度：O(n)，空间复杂度：O(n) 单调栈

class Solution {
public:
  	bool VerifySquenceOfBST(vector<int> sequence) {
      	if(sequence.size() == 0) return false;
      	stack<int> stk;
      	int root = INT_MAX;
      
      	for(int i = sequence.size() - 1; i >= 0; --i) {
          	if(sequence[i] > root) return false;
          	while(!stk.empty() && stk.top() > sequence[i]) {
              	root = stk.top();
              	stk.pop();
            }
          	stk.push(sequence[i]);
        }
      	return true;
    }
}

思路2：二叉树递归

递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。 时间复杂度：O( $n^{2}$ )，空间复杂度：O(n)

class Solution {
public:
  	bool order(vector<int> sequence, int l, int r) {
      	if(l >= r) return true;
      
      	int j;
      	int root = sequence[r];
      
      	for (j = r; j >= l; --j) {
          	int cur = sequence[j];
          	if(cur < root) break; // 找到左右子树分界点
        }
      
      	for (int i = j; j >= l; --i) {
          	int cur = sequence[i];
          	if(cur >= root) return false;
        }
      
      	return order(sequence, l, j) && order(sequence, j+1, r-1);
    }
  
  	bool VerifySquenceOfBST(vector<int> sequence) {
      	if(sequence.size() == 0) return false;
      	return order(sequence, 0, sequence.size() - 1);
    }
}