LeetCode 补充题 213. 二叉搜索树中第 k 小的节点
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 230. 二叉搜索树中第 K 小的元素
力扣保证树非空且 k 合法；本文额外约定空树或非法 k 返回 -1。
:::
给定二叉搜索树
root和整数k，返回按升序排列的第k个节点值。空树、
k <= 0或k超过节点数时返回-1。
示例 1：
输入：
root = [], k = 1
输出：-1
提示：
- 树满足严格二叉搜索树性质。
-
k从1开始计数。
题意分析
严格二叉搜索树的中序序列递增，只需数到第 k 个实际访问的节点。用显式栈可以找到答案后立即返回，无需保存完整有序序列。
解法：栈模拟中序遍历
核心思路
[!blue]
二叉搜索树的中序访问顺序就是节点值的升序，因此第 k 小就是第 k 次真正访问的节点。
stack保存已经沿左链走过、但自身尚未访问的祖先。先不断压入左孩子；左侧走完后弹栈，此时才访问当前节点并递减 k，再转到它的右子树。压栈只是等待，不应扣减排名。非法的
k <= 0先返回 -1；遍历条件同时检查当前节点和栈。两者都为空仍未命中，说明节点数不够，不应继续弹空栈。
解题步骤
- k<=0 时返回 -1，否则准备空栈。
- 沿当前节点的左链不断压栈，直到当前节点为空。
- 弹出栈顶并将 k 减一，归零时返回该节点值。
- 转向该节点的右子树继续；遍历耗尽仍未归零则返回 -1。
代码实现
class Solution {
public int kthSmallest(TreeNode root, int k) {
if (k <= 0) {
return -1;
}
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (--k == 0) {
return root.val;
}
root = root.right;
}
return -1;
}
}
func kthSmallest(root *TreeNode, k int) int {
if k <= 0 {
return -1
}
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
k--
if k == 0 {
return root.Val
}
root = root.Right
}
return -1
}
复杂度分析
- 时间复杂度：最坏 $O(n)$；合法 k 时可提前结束，耗时 $O(h+k)$，其中 $h$ 为树高。
- 空间复杂度：辅助栈 $O(h)$。
关键点总结
[!green]
用显式栈模拟中序遍历，在节点出栈时递减排名；仅在排名归零时返回，遍历结束仍未找到则返回 -1。
易错点总结
[!yellow]
- 压栈只是等待访问，只有出栈时才减少 k。
- 循环条件是当前节点非空或栈非空，不能要求两者同时非空。
- 节点不足时遍历结束返回 -1，不能继续弹空栈。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 二叉搜索树中序遍历得到升序节点，可复用第 k 次访问的计数；该题保证 k 合法，本题越界或空树时返回 -1。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！