二叉搜索树的后序遍历序列 - JZ23
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
数据范围： 节点数量满足 1 ≤ n ≤ 1000，节点上的值满足 1 ≤ val ≤ 10^4
示例：
-
输入：[1,6,3,2,5]
-
输出：false
-
输入：[1,3,2,6,5]
-
输出：true
解题思路
这道题考查二叉搜索树的性质和后序遍历的特点：
二叉搜索树的性质：
- 左子树的所有节点值
<根节点值 - 右子树的所有节点值
>根节点值
后序遍历的特点：
- 遍历顺序：左子树 → 右子树 → 根节点
- 序列的最后一个元素一定是根节点
核心思路：
- 数组最后一个元素是根节点
- 从前往后找到第一个大于根节点的位置，这是右子树的起始位置
- 检查右子树部分的所有节点是否都大于根节点
- 递归验证左子树和右子树
项目结构
.
├── go.mod # Go 模块定义
├── types.go # 辅助类型和工具函数
├── solution.go # 算法实现（你需要完成这个文件）
├── answer.go # 参考答案（练习后查看）
├── solution_test.go # 单元测试
└── README.md # 说明文档
使用方法
1. 实现算法
在 solution.go 文件中实现：
verifyPostorder(postorder []int) bool- 主要实现verifyPostorderRecursive(postorder []int) bool- 递归版本verifyPostorderIterative(postorder []int) bool- 迭代版本
2. 运行测试
go test -v
go test -bench=.
时间和空间复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归分治 | O(n²) | O(n) | 每层递归O(n)，递归深度O(n) |
| 单调栈 | O(n) | O(n) | 一次遍历，栈空间 |
知识点
- 二叉搜索树性质
- 后序遍历特点
- 递归分治思想
- 单调栈的应用
- 树的序列化验证
这是一个用于验证后序遍历序列是否为二叉搜索树(BST)的算法。让我详细解释一下：
单调栈法（最优解法）算法核心思想
这个算法巧妙地利用了 单调栈 和 逆序遍历 来模拟BST的构建过程。
关键洞察
- 后序遍历特点：左 → 右 → 根
- 逆序遍历：从右往左看后序序列，相当于 根 → 右 → 左 的遍历
- BST性质：左子树所有节点
<根节点<右子树所有节点
算法步骤详解
// 示例：postorder = [1, 3, 2, 6, 5]
// BST结构： 5
// / \
// 2 6
// / \
// 1 3
stack := []int{}
parent := 2147483647 // 当前节点的父节点值上界
// 从右往左遍历：5 → 6 → 2 → 3 → 1
for i := len(postorder) - 1; i >= 0; i-- {
current := postorder[i]
// 检查BST约束：当前节点不能大于其父节点的值
if current > parent {
return false
}
// 关键逻辑：当遇到比栈顶小的值时
// 说明要进入某个节点的左子树了
for len(stack) > 0 && current < stack[len(stack)-1] {
parent = stack[len(stack)-1] // 更新父节点约束
stack = stack[:len(stack)-1] // 出栈
}
stack = append(stack, current) // 当前节点入栈
}
执行过程示例
对于序列 [1, 3, 2, 6, 5]：
| 步骤 | current | stack状态 | parent | 操作说明 |
| ---- | ------- | --------- | ------ | -------------------------- |
| 1 | 5 | [5] | MAX | 根节点入栈 |
| 2 | 6 | [5,6] | MAX | 右子节点，直接入栈 |
| 3 | 2 | [2] | 5 | 2<6,2<5，出栈6,5，parent=5 |
| 4 | 3 | [2,3] | 5 | 3>2，直接入栈 |
| 5 | 1 | [1] | 2 | 1<3,1<2，出栈3,2，parent=2 |
为什么这样工作？
- 单调栈维护路径：栈中保存从当前节点到根的路径
- parent变量控制边界：确保左子树节点不超过其祖先节点的值
- 出栈时机：当遇到更小的值时，说明要进入左子树，需要找到正确的父节点
时间空间复杂度
- 时间复杂度：O(n) - 每个元素最多入栈出栈一次
- 空间复杂度：O(n) - 栈的空间
这个算法的精妙之处在于通过逆序遍历和单调栈，巧妙地模拟了BST的构建过程，同时维护了BST的约束条件。
单调栈是什么？
单调栈是一种特殊的栈数据结构，其中的元素按照某种单调性（递增或递减）排列。
基本概念
单调递增栈：从栈底到栈顶元素严格递增
单调递减栈：从栈底到栈顶元素严格递减
核心操作模式
// 单调递增栈的典型操作
stack := []int{}
for _, num := range nums {
// 维护单调性：当新元素破坏单调性时，弹出栈顶
for len(stack) > 0 && stack[len(stack)-1] >= num {
stack = stack[:len(stack)-1] // 出栈
}
stack = append(stack, num) // 入栈
}
图解示例
假设我们要构建单调递增栈，处理序列 [3, 1, 4, 2, 5]：
输入: 3
栈: [3]
↑栈顶
输入: 1 (1 < 3，需要出栈3)
栈: [1]
↑栈顶
输入: 4 (4 > 1，直接入栈)
栈: [1, 4]
↑栈顶
输入: 2 (2 < 4，需要出栈4)
栈: [1, 2]
↑栈顶
输入: 5 (5 > 2，直接入栈)
栈: [1, 2, 5]
↑栈顶
典型应用场景
1. 下一个更大元素
func nextGreaterElement(nums []int) []int {
stack := []int{}
result := make([]int, len(nums))
// 从右往左遍历
for i := len(nums) - 1; i >= 0; i-- {
// 维护单调递减栈
for len(stack) > 0 && stack[len(stack)-1] <= nums[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
result[i] = -1
} else {
result[i] = stack[len(stack)-1]
}
stack = append(stack, nums[i])
}
return result
}
2. 最大矩形面积
func largestRectangleArea(heights []int) int {
stack := []int{} // 存储索引
maxArea := 0
for i, h := range heights {
// 维护单调递增栈
for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := i
if len(stack) > 0 {
width = i - stack[len(stack)-1] - 1
}
maxArea = max(maxArea, height * width)
}
stack = append(stack, i)
}
return maxArea
}
在BST验证算法中的作用
回到原问题，单调栈在BST验证中的作用：
// 使用单调递增栈
for i := len(postorder) - 1; i >= 0; i-- {
current := postorder[i]
// 当current小于栈顶时，破坏了单调性
// 需要出栈直到恢复单调性
for len(stack) > 0 && current < stack[len(stack)-1] {
parent = stack[len(stack)-1] // 记录被弹出的节点
stack = stack[:len(stack)-1]
}
stack = append(stack, current)
}
这里的单调栈作用：
- 维护从当前节点到根的路径
- 快速找到左子树的根节点（当单调性被破坏时）
- 利用栈的后进先出特性模拟树的层级关系
为什么选择单调栈？
- 高效性：每个元素最多入栈出栈一次，O(n)时间复杂度
- 自然的边界维护：栈顶总是最近的"候选答案"
- 状态压缩：用栈隐式维护了复杂的层级关系
单调栈是解决"寻找下一个更大/更小元素"类问题的经典工具！