[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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

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 并发能力的因素二、