[LeetCode]Kth Smallest Element in a BST
发布日期:2021-11-22 02:48:59
浏览次数:3
分类:技术文章
本文共 731 字,大约阅读时间需要 2 分钟。
Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
题解:使用DFS,BTS的结构是root.left<root<root.right,采用中序遍历,可以得到k小的值。
code:
public class Solution { private int value; private int index; public int kthSmallest(TreeNode root, int k) { index = 0; dfs(root, k); return value; } public void dfs(TreeNode root, int k) { if(root == null) return; dfs(root.left, k); index++; if (index == k) { value = root.val; return; } dfs(root.right, k); }}
转载地址:https://blog.csdn.net/zxdfc/article/details/48765401 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月01日 10时38分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【Android平台】 Alljoyn学习笔记二 编译自带的demo的步骤
2019-04-26
【Android平台】 Alljoyn学习笔记四 Android Core API参考
2019-04-26
【Alljoyn】Alljoyn学习笔记五 AllJoyn开源技术基础概念解析
2019-04-26
【Alljoyn】 Alljoyn学习笔记六 Alljoyn基本概念
2019-04-26
【Alljoyn】 Alljoyn学习笔记七 Alljoyn瘦客户端库介绍
2019-04-26
【Android】Activity生命周期
2019-04-26
【Android】Activity的四种launchMode
2019-04-26
【Android】Activity的task相关
2019-04-26
【Android】 Intent应用详解
2019-04-26
【Android】 Intent详解
2019-04-26
【Android】 常用的Intent
2019-04-26
Android中AsyncTask的简单用法
2019-04-26
【Android】 Android中Log调试详解
2019-04-26
【Android】Android中WIFI开发总结(二)
2019-04-26
【Android】Android之WiFi开发应用示例
2019-04-26
【Android】 Android adb常见问题整理
2019-04-26
【Android】 Android体系结构图
2019-04-26
【Android】 Android中spinner下拉列表的使用
2019-04-26
说说在 python 中,如何删除左右两边不需要的字符
2019-04-26