当前位置：首页 > news >正文

Leetcodehot 力扣热题100 二叉搜索树中第 K 小的元素

news 2025/6/21 16:34:57

class Solution {
public:int res; // 用于存储第 k 小的元素int kthSmallest(TreeNode* root, int k) {inorder(root, k);  // 进行中序遍历并找到第 k 小的元素return res;  // 返回结果}private:// 中序遍历：遍历树的左子树、根节点和右子树void inorder(TreeNode* root, int &k) {if (root != nullptr) {  // 如果当前节点不是空节点inorder(root->left, k);  // 递归遍历左子树if (--k == 0)  // 每访问一个节点，减少 k，直到 k 减到 0res = root->val;  // 当 k == 0 时，记录当前节点的值为第 k 小的元素inorder(root->right, k);  // 递归遍历右子树}}
};

思路：

这个问题要求你找到二叉搜索树（BST）中的第 k 小的元素。二叉搜索树的性质是：对于每个节点，左子树的值都比该节点小，右子树的值都比该节点大。因此，通过中序遍历（左-根-右）遍历 BST，节点会按升序排列。所以第 k 小的元素就是中序遍历中的第 k 个元素。

详细步骤：

1. 中序遍历：从左子树开始遍历，访问根节点，再遍历右子树。由于是 BST，节点会按升序排列。

2. 在遍历过程中，每访问一个节点，就把计数器 k 减 1，当 k == 0 时，当前节点的值就是第 k 小的元素，记录下这个值。

3. 使用递归的方式遍历树，同时传递 k，这样可以保证每次递归的 k 都是最新的值。

解释：

• int &k：

• 为什么要加 &：k 变量是通过引用传递的，这样可以确保递归过程中 k 的值是共享的，能够在递归的每一层中更新。如果没有使用引用传递，k 的值会被复制，每一层递归中的 k 都是一个副本，递归返回时不会影响原来的 k 值。因此，使用引用可以保证每次递归时，k 的值是动态变化的，直到找到第 k 小的元素。

• 引用的作用：通过引用传递，k 在每次递归时的变化会反映到父级递归中，这样就能准确计算出当前是第几个元素。

代码运行步骤：

1. kthSmallest 被调用时，传入根节点和 k，然后调用 inorder 函数开始递归遍历。

2. 递归从左子树开始，直到遍历到根节点，递归继续到右子树。

3. 每遍历一个节点，k 减 1，当 k == 0 时，记录下当前节点的值。

4. 中序遍历会按升序访问所有节点，因此一旦 k == 0，记录的值就是第 k 小的元素。

例子：

假设有如下二叉搜索树：

/ \

3 6

/ \

2 4