LeetCode题目之腾讯精选练习（50题）：二叉搜索树中第K小的元素

太过爱你忘了你带给我的痛 2023-10-10 09:41 12阅读 0赞

# 题目 #

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 **k** 个最小的元素。

**说明** ：  
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

**示例 1** :

输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 1

**示例 2** :

输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 3

**进阶**：  
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

## 算法实现 ##

private int res, count;
    public int KthSmallest(TreeNode root, int k)
    {
        
        count = k;
        inorder(root);
        return res;
    }
    private void inorder(TreeNode root)
    {
        
        if (root == null || count == 0) return;
        inorder(root.left);
        if (--count == 0) res = root.val;
        inorder(root.right);
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 100 msms, 在所有 C\# 提交中击败了100.00%的用户  
**内存消耗** : 27 MB, 在所有 C\# 提交中击败了9.09%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

又是关于搜索二叉树的题，这次利用到它的特性：中序遍历为排序数组。（我还是不知道这个特性，看来有必要系统学习一下二叉树了）看了官方的题解，看懂了，但如果让我设计的话可能不太行，因为对二叉树了解太浅了。。。。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019092417072953.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70