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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

数据范围

数组长度 $[0, 1000]$ 。

样例

输入：[4, 8, 6, 12, 16, 14, 10]输出：true

算法思路：

基本思想：
- 利用后序遍历特性：序列最后一个元素为根节点
- 递归验证左子树所有节点 < 根节点 < 右子树所有节点
验证过程：
- 基准条件：当子序列长度 ≤ 1 时返回true
- 划分左右子树：
  1. 定位第一个≥根节点的元素作为分界点
  2. 验证右子树部分全部＞根节点
- 递归验证：
  - 左子树区间[l, k-1]
  - 右子树区间[k, r-1]（排除末尾根节点）
实现特点：
- 使用类成员变量seq避免参数传递
- 原地划分不需要额外空间

复杂度类型	分析结果	说明
时间复杂度	O(n²)	最坏情况下（链式树）需要n+(n-1)+…+1次比较
空间复杂度	O(n)	递归栈深度最大为树高，最坏情况下（链式树）为O(n)

最优情况（平衡二叉树）：O(nlogn)
最坏情况（单支树）：O(n²)
平均情况：O(nlogn)

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