LeetCode怎么找出二叉搜索树中第K小的元素

发布时间:2021-12-15 14:54:07 作者:小新
来源:亿速云 阅读:134

这篇文章主要介绍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小的元素

以上是“LeetCode怎么找出二叉搜索树中第K小的元素”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. 在链表中找出倒数第K个节点
  2. leetCode如何求链表中倒数第k个节点

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:LeetCode怎样不用加减乘除做加法

下一篇:LeetCode怎么求最后一个单词的长度

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》