图解LeetCode——230. 二叉搜索树中第K小的元素

爪哇缪斯

发布于 2023-09-06 13:40:38

1610

发布于 2023-09-06 13:40:38

文章被收录于专栏：爪哇缪斯

一、题目

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

二、示例

2.1> 示例 1：

【输入】root = [3,1,4,null,2], k = 1 【输出】1

2.2> 示例 2：

【输入】root = [5,3,6,2,4,null,null,1], k = 3 【输出】3

提示：

树中的节点数为 n
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

三、解题思路

根据题目描述，我们要在题目给定的二叉搜索树中寻找第K小的元素。那么题目中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：

【若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值；【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；

所以，我们可以采用中序遍历的方式，因为 中序遍历 + 二叉搜索树，最终输出的就是一个递增的元素集合。为了统计出当前元素是第K小的元素，我们需要创建一个全局的计数器count，只有当count等于k之后，那么就表示我们已经找到了第K小的元素了。

那么如果我们找到了第K小的元素了之后，如果让后续的遍历可以快速结束呢，我们还可以通过创建一个全局变量result，默认值为-1，当我们找到了第K小的元素之后，将该节点的值赋值给result，那么在后续的遍历过程中，如果我们发现result不等于-1了，则表示已经找到了第K小的元素了，那么直接返回即可。

以上就是本题的解题思路，为了便于理解，我们以输入为root = [5,3,6,2,4,null,null,1], k = 3为例，寻找第3小的元素。具体操作请见下图所示：

四、代码实现

class Solution {
    int count = 0, result = -1;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null || result != -1) return result;
        kthSmallest(root.left, k);
        if (++count == k) result = root.val;  
        kthSmallest(root.right, k);
        return result;
    }
}