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

题号：NC3728
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

数据范围：节点数量 $0 \le n \le 1000$ ，节点上的值满足 $1 \le val \le 10^{5}$ ，保证节点上的值各不相同
要求：空间复杂度 $O(n)$ ，时间时间复杂度 $O(n^2)$

提示：

1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

4.参考下面的二叉搜索树，示例 1

示例1

复制

[1,3,2]

复制

true

是上图的后序遍历 ，返回true

示例2

复制

[3,1,2]

复制

false

不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false

示例3

复制

[5,7,6,9,11,10,8]

复制

true