剑指offer32_二叉搜索树的后序遍历序列

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

---

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

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

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

数据范围

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

样例

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

---

算法思路 ：

1. 基本思想：

   • 利用后序遍历特性：序列最后一个元素为根节点
   • 递归验证左子树所有节点 < 根节点 < 右子树所有节点

2. 验证过程：

   • 基准条件：当子序列长度 ≤ 1 时返回true
   • 划分左右子树：
     1. 定位第一个≥根节点的元素作为分界点
     2. 验证右子树部分全部＞根节点
   • 递归验证：
     • 左子树区间[l, k-1]
     • 右子树区间[k, r-1]（排除末尾根节点）

3. 实现特点：

   • 使用类成员变量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);}
};

算法优化方向 ：

1. 单调栈解法：可优化至O(n)时间复杂度
2. 剪枝策略：当发现非法右子树节点时立即终止递归
3. 迭代实现：用栈替代递归可优化空间复杂度为O(1)（尾递归优化）