230. 二叉搜索树中第 K 小的元素
3 min
题目
解法：中序遍历
思路
利用 BST 中序遍历呈升序的特性，通过计数找到第 k 个访问的节点。
BST 的性质保证左子树所有节点值小于根节点，根节点小于右子树。中序遍历（左-根-右）必然产生严格升序序列，因此访问顺序中的第 k 个节点即为全局第 k 小的元素。算法维护一个计数器，在访问节点时递减，当计数器归零时立即返回，确保不会错过目标且避免多余遍历。
- Step 1: 递归遍历左子树
- Step 2: 检查计数，若已找到结果则提前返回
- Step 3: 访问当前节点，计数减一，若计数为 0 则记录结果并返回
- Step 4: 递归遍历右子树
复杂度
- 时间复杂度: ，最坏情况下需遍历所有节点。
- 空间复杂度: ，最坏情况下递归栈深度为树的高度。
代码
class Solution {
private:
int res;
int count;
public:
int kthSmallest(TreeNode* root, int k) {
count = k;
traverse(root);
return res;
}
void traverse(TreeNode* root) {
if (root == nullptr) return;
// 1. 中序遍历：先左
traverse(root->left);
// 2. 这里的逻辑：一旦找到结果，就不再处理后续节点
if (count == 0) return;
// 3. 访问当前节点
count--;
if (count == 0) {
res = root->val;
class Solution {
private:
int res;
int count;
public:
int kthSmallest(TreeNode* root, int k) {
count = k;
traverse(root);
return res;
}
void traverse(TreeNode* root) {
if (root == nullptr) return;
// 1. 中序遍历：先左
traverse(root->left);
// 2. 这里的逻辑：一旦找到结果，就不再处理后续节点
if (count == 0) return;
// 3. 访问当前节点
count--;
if (count == 0) {
res = root->val;
return;
}
// 4. 最后右
traverse(root->right);
}
};