每日一题 230二叉搜索树中第K小的元素(中序遍历)

这篇具有很好参考价值的文章主要介绍了每日一题 230二叉搜索树中第K小的元素(中序遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

示例 1:

每日一题 230二叉搜索树中第K小的元素(中序遍历),算法,数据结构,leetcode

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:

每日一题 230二叉搜索树中第K小的元素(中序遍历),算法,数据结构,leetcode文章来源地址https://www.toymoban.com/news/detail-694063.html

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;// 接收答案
    private int p; // 接收k
    public int kthSmallest(TreeNode root, int k) {
        p = k;
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode root) {
        //中序遍历
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (--p == 0) {
            ans = root.val;// 更新答案
        }
        dfs(root.right);
    }
}

到了这里,关于每日一题 230二叉搜索树中第K小的元素(中序遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题:leetcode 1448 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 思路

    2024年02月11日
    浏览(41)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 显然

    2024年02月11日
    浏览(37)
  • 2023-08-25 LeetCode每日一题(统计二叉树中好节点的数目)

    点击跳转到题目位置 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是 [1, 10 5 ] 。 每个节点权值的范围是 [-10

    2024年02月11日
    浏览(36)
  • 有序矩阵中第 K 小的元素

    有序矩阵中第 K 小的元素 每行和每列元素均按升序排序 找到一个内存复杂度优于 O(n²) 的解决方案 使用二分查找,思路为: (1)因为左上角的元素值更小,右下角的元素值更大,先将left设置为左上角元素的值,right设置为右下角元素的值; (2)判断不大于left和right中间值

    2024年01月20日
    浏览(74)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目(2023.8.25 C++)

    目录 1448. 统计二叉树中好节点的数目 题目描述: 实现代码与解析: dfs 原理思路:         给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例

    2024年02月11日
    浏览(39)
  • 【优先队列】378. 有序矩阵中第 K 小的元素

    初始化最大堆: 创建一个最大堆的优先队列,这使得队列中的元素按照降序排列。 遍历矩阵并更新队列: 通过嵌套的循环遍历二维矩阵中的每一个元素,将元素添加到最大堆中。 控制队列大小: 在添加元素后,检查队列的大小是否已经达到了k。如果已经达到,而且当前遍

    2024年01月22日
    浏览(51)
  • LeetCode 378 有序矩阵中第K小的元素

    LeetoCode地址: . - 力扣(LeetCode) 题解内容大量转载于:. - 力扣(LeetCode) 题意很直观,就是求二维矩阵中所有元素排序后第k小的数。 该写法不再赘述,维护一个大小为k的小顶堆,遍历矩阵所有元素进行入堆操作。 时间复杂度:O(nlogk) 空间复杂度:O(k) 由于矩阵在行和列上都是

    2024年04月12日
    浏览(37)
  • java数据结构与算法刷题-----LeetCode378. 有序矩阵中第 K 小的元素

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 已知矩阵相对有序,可以用二分搜索,不过和一维数组排序不同,这是二维的 每一行都递增,每一列也是递增,所以每

    2024年01月23日
    浏览(51)
  • 【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置

    ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记: 初阶数据结构专栏 Linux被操作记: Linux专栏 LeetCode刷题掉发记: LeetCode刷题 算法: 算法专栏  C++头疼记: C++专栏 计算机

    2024年02月08日
    浏览(55)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包