( “树” 之 BST) 230. 二叉搜索树中第K小的元素 ——【Leetcode每日一题】

灰太狼 2024-03-23 15:14 13阅读 0赞

> 二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。  
> 二叉查找树中序遍历有序。

### 230. 二叉搜索树中第K小的元素 ###

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

##### 示例 1： #####

![在这里插入图片描述][d7747ad418a94ebcaf5c7de94daf555b.png]

> 输入：root = \[3,1,4,null,2\], k = 1  
> 输出：1

##### 示例 2： #####

![在这里插入图片描述][98cfd86d5fdc4959b11d7bc4c0ac6648.png]

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

**提示：**

*  树中的节点数为 n 。
 *   1 < = k < = n < = 1 0 4 1 <= k <= n <= 10^4 1<=k<=n<=104
 *   0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104

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

#### 思路：（中序遍历） ####

二叉搜索树中序遍历就是有序的，所以中序遍历该树，第`k`个节点的`val`即为第`K`小的元素。

**法一：递归**、**法二：迭代**

具体思路请看：[94. 二叉树的中序遍历][94.]

#### 代码：(Java、C++) ####

**法一：递归**  
**Java**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        private int cnt = 0;
        private int ans;
        public int kthSmallest(TreeNode root, int k) {
        
            cnt = k;
            dfs(root);
            return ans;
        }
        public void dfs(TreeNode root){
        
            if(root == null) return;
            dfs(root.left);
            if(--cnt == 0) {
        
                ans = root.val;
                return;
            }
            dfs(root.right);
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * 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 cnt = 0;
        int ans;
        int kthSmallest(TreeNode* root, int k) {
        
            cnt = k;
            dfs(root);
            return ans;
        }
        void dfs(TreeNode* root){
        
            if(root == nullptr) return;
            dfs(root->left);
            if(--cnt == 0){
        
                ans = root->val;
                return;
            }
            dfs(root->right);
        }
    };

**法二：迭代**  
**Java**

class Solution {
        
        public int kthSmallest(TreeNode root, int k) {
        
            Stack<TreeNode> stk = new Stack<>();
            while(root != null || !stk.isEmpty()){
        
                while(root != null){
        
                    stk.push(root);
                    root = root.left;
                }
                root = stk.pop();
                if(--k == 0){
        
                    return root.val;
                }
                root = root.right;
            }
            return 0;
        }
    }

**C++**

class Solution {
        
    public:
        int kthSmallest(TreeNode* root, int k) {
        
            stack<TreeNode*> stk;
            while(root != nullptr || !stk.empty()){
        
                while(root != nullptr){
        
                    stk.push(root);
                    root = root->left;
                }
                root = stk.top();
                stk.pop();
                if(--k == 0){
        
                    return root->val;
                }
                root = root->right;
            }
            return 0;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][58b40ab002d745bf8ac0edeb4f99c32b.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是二叉树的节点数。最坏的情况下为`k=n`每一个节点恰好被遍历一次。
 *  **空间复杂度**： O ( n ) O(n) O(n)，为递归或迭代过程中栈的开销，平均情况下为  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，最坏情况下树呈现链状，为  O ( n ) O(n) O(n)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[d7747ad418a94ebcaf5c7de94daf555b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3368343c90734c0ca99d3b357de5fc28.png
[98cfd86d5fdc4959b11d7bc4c0ac6648.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8d83ea1b1070454097ba356201089685.png
[94.]: https://blog.csdn.net/weixin_43412762/article/details/130243933?spm=1001.2014.3001.5501
[58b40ab002d745bf8ac0edeb4f99c32b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3653b887dc824abebc0b13df417503f4.png
[Link 1]: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?orderBy=most_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes
[leetCode]: http://t.csdn.cn/kQLJO