购物车中没有产品。
230. 二叉搜索树中第 K 小的元素（中等）
Blind 75 › 230. 二叉搜索树中第 K 小的元素（中等） （第 8 章）
题目
给定一棵二叉搜索树（BST）的根节点 root 和一个整数 k（从 1 开始计数），请返回这棵树所有节点值按从大到小排序后的第 k 个节点的值。
二叉搜索树有一个“天然排序”的性质：按中序（左 → 根 → 右）访问节点，得到的序列就是按值升序排列的（若允许重复值则是非递减序列，照样按位置数即可）。所以“第 k 小”等价于“中序序列的第 k 项”。
自造示例：root = [5,3,6,2,4,null,7]（数组中 null 表示空节点），k = 3。
5
/
3 6
/
2 4 7
中序序列为 [2,3,4,5,6,7]，第 3 项是 4，所以答案为 4。
约束：节点数 1 ~ 104；1 ≤ k ≤ 节点数；节点值 0 ~ 104。
思路
一句话：中序遍历就是天然排序，第 k 小 = 中序遍历时访问到的第 k 个节点。
先想最直白的：把整棵树遍历一遍，把所有节点值塞进数组，排序后取 arr[k - 1]。时间 O(n log n)、空间 O(n)，能过，但完全浪费了 BST“本来就排好序”的信息。
关键观察：BST 的中序遍历（左 → 根 → 右）本身就是升序输出。于是问题从“在一堆数里找第 k 小”退化成“数着步子走中序，到第 k 步停下”——既不用排序，还能在找到答案后提前终止，不必看完右子树后半段。
两种等价写法：
- 递归：左子树 → 访问当前节点（
k减 1，减到 0 就是答案）→ 右子树；加一个“已找到”标志提前剪枝。 - 迭代 + 显式栈：一路向左压栈，弹出时算一次访问，减到 0 返回，否则进入右子树。它在 Python 里还能避开递归深度限制。
两者本质完全一样：都只是把“左-根-右”这个状态机走一遍，并给“根”那一拍装了一个计数器。
解法
主解法用一次带计数器的中序遍历。迭代版三件事反复做：
- 把当前节点以及它的整条左链压栈：
stack存“还没访问的根”。 - 弹出栈顶，这就是当前中序访问节点，执行
k -= 1。 - 若
k == 0，直接返回该节点值；否则转到它的右子树，回到步骤 1。
递归版则是“左递归 → 访问当前 → 右递归”，并在找到后用 found 标记不再向下钻。以自造示例跟踪：
| 访问次序 | 访问到的节点 | k 变化 | 结论 |
|---|---|---|---|
| 1 | 2 | 3 → 2 | 继续 |
| 2 | 3 | 2 → 1 | 继续 |
| 3 | 4 | 1 → 0 | 返回 4 |
中序序列 [2,3,4,5,6,7] 的第 3 项是 4，正好在第 3 次访问时命中。
下图把上面 3 个步骤串成流程，并逐步演示：
C++
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right)
: val(x), left(left), right(right) {}
}; class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int ans = 0;
bool found = false; // 找到后整棵树提前剪枝
inorder(root, k, ans, found);
return ans;
} private:
void inorder(TreeNode* node, int& k, int& ans, bool& found) {
if (node == nullptr || found) return; inorder(node->left, k, ans, found);
if (found) return; --k; // 先减再判，避免差一位
if (k == 0) {
ans = node->val;
found = true;
return;
} inorder(node->right, k, ans, found)本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。
还没有评论，来说两句？