230. 二叉搜索树中第K小的元素（BST）_编写一个程序要求返回在bst中第k小的元素。-程序员宅基地

技术标签：力扣

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

题目
解题思路
代码

题目

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

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

在这里插入图片描述

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

解题思路

、这题可以考虑到用中序遍历，把中序遍历的结果依次存放在 list中，这样第1小的就是存放在list中的下标为0的位置，所以求第k小的，只要去list中拿到k-1位置的值。

总结一下：
1、树的题先写出左右递归的模板
2、根据题目要求看是前序、中序还是后序遍历，在对应位置填代码
3、本题利用BST中序遍历的特性找元素，所以应该是中序遍历，在左右递归中间填代码

还是我们之前说的“找到一个节点要做的事情，剩下的交给递归框架”，这里只不过要分一下情况，

即：一个节点到底该在那个位置做事情，即前序，中序，还是后续，就分别在递归框架的前面，中间，后面写该节点要做的事情。

代码

class Solution {
    
    public int kthSmallest(TreeNode root, int k) {
    
        List<Integer> list=new ArrayList<>();
        depth(root,list);//经过这个操作，这棵树已经按照中序遍历存放在list中，我们求第1小的，就是list中的第一个元素，即下标为0.

        return list.get(k-1);

    }
    public void depth(TreeNode root, List<Integer> list){
    
        if(root==null){
    
            return ;
        }
         depth(root.left,list);
         //这题应该用中序遍历
        list.add(root.val);//把中序遍历的结果依次存放在list中
         depth(root.right,list);

    }
}

本文链接：https://blog.csdn.net/qq_21040559/article/details/111055010

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Linux 磁盘管理_emmc 启动,怎么查看内核文件系统的分区大小-程序员宅基地

文章浏览阅读1.6k次。Linux分区实践_emmc 启动,怎么查看内核文件系统的分区大小

调用 jquery 的replace函数实现 replaceAll 效果-程序员宅基地

文章浏览阅读6.5k次。jquery 不支持 replaceAll使用 .replace(new RegExp(",","g"), "") 为变种写法懂得就懂了不懂的我也没办法<td class="box" align="center"> 金额：<b id="purchValidationSum">0.00</b>

生物信息-McScan（Python-jcvi）共线性画图-程序员宅基地

文章浏览阅读4.4k次，点赞4次，收藏14次。发现有人竟然直接拷贝了我的文章内容，还说是原创（几百的访问量，这个作者的其他作品普遍访问量个位数）。没有找到维权入口，我想试着再发布一次文章进行维权，原文始发于博客园（abysw）。我用的自己的已发表文章和未发表文章做的展示。下面是我博客园的原文：比较基因组学中，共线性的分析的图无疑是最漂亮的。共线性分析可以很好地解释进化关系和多倍化事件。本文主要介绍的是唐老师的Python版McScan（jcvi工具包），这个包很强大，但是其功能在官网的说明并不详细，在众人的博客中也比较零散。_mcscan

logisim计组实验三补码表示实验答案浮点数表示实验汉字编码实验_logisim汉字编码-程序员宅基地

文章浏览阅读4.4k次，点赞6次，收藏40次。本博客为谭志虎老师的《计算机组成原理实践教程——从逻辑门到CPU》实验记录，因为目前网上并没有本书的答案，错漏在所难免，请各位帮忙指正。文章目录补码表示实验答案1234实验思考实验四浮点数表示实验123456789汉字编码实验补码表示实验答案1答案：1 2 4 8 16 32 64 128 256 512提示：二进制数做位运算看看2#include "stdio.h"void ..._logisim汉字编码

MediaPlayer播放流程_onqueuefilled-程序员宅基地

文章浏览阅读1.3k次，点赞5次，收藏14次。MediaPlayer播放流程setDataSource流程应用通过setDataSource(FileDescriptor fd, long offset, long length)这个方法将音频资源设置下来，setDataSource 将path 变成文件描述符fd，最后将fd通过native的_setDataSource设置到下面去Android_media_MediaPlayer.cpp在JNI注册表中将_setDataSource方法映射成 an..._onqueuefilled

python吃豆人代码_敲代码学Python：CS188之吃完所有角落的豆豆-程序员宅基地

文章浏览阅读1.7k次。先上视频：吃完所有角落的豆豆视频演示https://www.zhihu.com/video/1177971208993325056简单说一下我的思路：搜索状态的表达是搜索算法中的重要部分，在本题中，为了记录下吃豆人的吃豆过程，我把吃豆人所经过的包含豆豆的坐标放在搜索状态中，这样就可以从搜索状态中判定它是否完成了当前地图的任务目标。贴代码吧：class CornersProblem(search.S..._如何在吃豆人里用代码吃完所以豆

随便推点

拯救狗屎代码：基于 Gitlab 的代码审查，简单实用_git的approvers-程序员宅基地

文章浏览阅读1.1k次。作者：刘凯_7013https://www.jianshu.com/p/5d764b52ea88code review 的目的是提高代码质量，减少开发bug，俗话说，三人行必有我师，众人拾柴火焰高。gitlab提供了code review机制，对基于gitlab的code review，直接以具体例子的形式做个实践总结。gitlab提供了两种代码merge机制：1）在本地将源分支(Source branch)代码合并到目标分支（Target branch），然后Push到目标分支（Target._git的approvers