算法-二叉搜索树中第K小的元素

Myth丶恋晨 2023-10-09 20:28 3阅读 0赞

#### 文章目录 ####

*  1. 查找第 K 小元素
 *  2. 解法

## 1. 查找第 K 小元素 ##

给定一个二叉搜索树的根节点 root 和一个整数 k ，查找树中第 k 个最小元素（从 1 开始计数），[LeetCode原题][LeetCode]

![在这里插入图片描述][0247752e21ba407b87f7e4db54777acc.png_pic_center]

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

## 2. 解法 ##

> 二叉搜索树的中序遍历为有序数组，借助栈结构将树的左子树入栈，直到叶节点为空开始出栈，此时对出栈元素进行计数即可

public int kthSmallest(TreeNode root, int k) {
        
            if (null == root) {
        
                return 0;
            }
            int count = 0;
            Stack<TreeNode> stack = new Stack<>();
            while (null != root || !stack.empty()) {
        
                if (null != root) {
        
                    stack.push(root);
                    root = root.left;
                } else {
        
                    root = stack.pop();
                    count++;
                    if (count == k) {
        
                        return root.val;
                    }
                    root = root.right;
                }
            }
            return 0;
        }

[LeetCode]: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
[0247752e21ba407b87f7e4db54777acc.png_pic_center]: https://img-blog.csdnimg.cn/0247752e21ba407b87f7e4db54777acc.png#pic_center

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-二叉搜索树中第K小的元素

文章目录 1. 查找第 K 小元素 2. 解法 1. 查找第 K 小元素给定一个二叉搜索树的根节点 root 和一个整数 k ，查找树中第 k 个最

Myth丶恋晨/ 2023年10月09日 20:28/ 0 赞/ 4 阅读

相关 LeetCode_二叉搜索树_中等_230.二叉搜索树中第K小的元素

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中

逃离我推掉我的手/ 2023年10月06日 22:27/ 0 赞/ 28 阅读

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

题目来源 [230. 二叉搜索树中第K小的元素][230. _K] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naG

快来打我*/ 2022年12月22日 08:51/ 0 赞/ 133 阅读

相关【LeetCode 230】二叉搜索树中第K小的元素

题目描述给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树

r囧r小猫/ 2022年11月30日 04:03/ 0 赞/ 139 阅读

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

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

深碍√TFBOYSˉ_/ 2022年10月08日 00:51/ 0 赞/ 141 阅读

相关 LeetCode230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 `kthSmallest` 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

╰半夏微凉°/ 2022年05月06日 04:26/ 0 赞/ 157 阅读

相关 leetcode 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。示

朴灿烈づ我的快乐病毒、/ 2022年03月18日 02:44/ 0 赞/ 138 阅读

相关 leetcode:230. 二叉搜索树中第K小的元素

题目: 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元

蔚落/ 2022年03月09日 08:12/ 0 赞/ 166 阅读

相关 golang 实现二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤

ゝ一纸荒年。/ 2022年03月08日 11:26/ 0 赞/ 64 阅读

相关 LeetCode230.二叉搜索树中第K小的元素

参考链接：[https://blog.csdn.net/yuanliang861/article/details/84640069][https_blog.csdn.net_y

青旅半醒/ 2022年02月15日 08:51/ 0 赞/ 178 阅读