您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍LeetCode怎么找出二叉搜索树中第K小的元素,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
1,问题简述
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
2,示例
示例 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
3,题解思路
使用二叉树的中序遍历方式进行解决
4,题解程序
import java.util.ArrayList;
import java.util.List;
public class KthSmallestTest3 {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(3);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(4);
TreeNode t4 = new TreeNode(2);
t1.left = t2;
t1.right = t3;
t2.right = t4;
int k = 1;
int kthSmallest = kthSmallest(t1, k);
System.out.println("kthSmallest = " + kthSmallest);
}
private static List<Integer> list = new ArrayList<>();
public static int kthSmallest(TreeNode root, int k) {
if (root == null) {
return 0;
}
dfs(root);
return list.get(k - 1);
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
dfs(root.left);
}
list.add(root.val);
if (root.right != null) {
dfs(root.right);
}
}
}
5,题解程序图片版
以上是“LeetCode怎么找出二叉搜索树中第K小的元素”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。