[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索

本文主要是介绍[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、题目描述

二、整体思路

三、代码


一、题目描述

题目地址

二、整体思路

        大根堆/优先队列

        看到第K小的元素(Top K)问题,第一时间想到快速排序/大根堆/优先队列。比较简单的思路是把所有结点加入到优先队列,然后重复出队列操作使得队列中元素数量为k,此时队首元素即为第K小的元素。优先队列的数据结构是大根堆,在遇见比堆顶小的元素时直接替换堆顶并维护大根堆,当大根堆元素数量为K时此时堆顶的意义为全体元素中最小的K个数中最大的数,也就是第K小的数。

快排代码在此题不太适合,和二叉搜索树的特性没什么联系了。

        DFS深度优先搜索

        二叉搜索树的特性是每个节点比其左子树所有节点要大,比其右子树所有节点要小。那么我们可以用DFS优先把左子树遍历完再遍历右子树,回溯的同时令K-1。当K==1时遍历到的结点即为第K小的结点。(二叉搜索树的前序遍历即按升序顺序把所有节点遍历一遍,DFS与前序遍历有相同之处)

        要注意的是需要在类内设立两个成员变量来暂存当前K值和当前第K的元素值。K不可以作为参数传入dfs。

三、代码

/*** 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 {//大根堆/优先队列PriorityQueue<Integer> pq=new PriorityQueue<>((x,y)->(y-x));public int kthSmallest(TreeNode root, int k) {preorder(root);while(pq.size()!=k){pq.poll();}return pq.peek();}public void preorder(TreeNode node){if(node==null){return;}pq.add(node.val);preorder(node.left);preorder(node.right);return;}
}
/*** 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 {//dfsint tar;int k;public int kthSmallest(TreeNode root, int k) {this.k=k;dfs(root);return tar;}public void dfs(TreeNode node){if(node==null || k<=0){return;}dfs(node.left);if(k==1){tar=node.val;k--;return;}k--;dfs(node.right);}
}

这篇关于[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110684

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3