首页 > 其他分享 >二叉树 查找第k大的数

二叉树 查找第k大的数

时间:2022-08-20 16:02:05浏览次数:59  
标签:numOfNodes 删除 二叉 查找 二叉树 节点

改造方法

需在节点N中记录以节点N为根的子树的节点数numOfNodes,

根节点记录整颗树的节点数目,

则若根节点的左子树的numOfNodes刚好为k-1,那这个根节点的值即为目标值。

注意递归时,k需变化,因为有可能在右子树上

使用二叉堆

法一

将数组构建成一个二叉堆(这时要求最大的在上面),

然后执行k次删除最小元,则最后一次删除得到的数即为第k大的数

法二

仅构建一个大小为K的堆(最小的在上面)

堆满后,每次只添加比根更大的元素,则结束后 堆顶元素即为第K大的数

标签:numOfNodes,删除,二叉,查找,二叉树,节点
From: https://www.cnblogs.com/xiang-jin-hua/p/16599379.html

相关文章

  • 二分法查找
    importrandomclassSearch(object):defbinary_search(self,data,value):"""二分查找迭代法实现:paramdata:list待查找序列......
  • 2022-8-20 每日一题-二叉树-递归
    654.最大二叉树难度中等499收藏分享切换为英文接收动态反馈给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个......
  • 654. 最大二叉树
    654.最大二叉树给定一个不重复的整数数组 nums。 最大二叉树 可以用下面的算法从 nums递归地构建:创建一个根节点,其值为 nums中的最大值。递归地在最大值......
  • LeetCode/最大二叉树
    给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点,其值为nums中的最大值递归地在最大值左边的子数组前缀上构建......
  • 【LeetCode】102.二叉树的层序遍历
    【LeetCode】102.二叉树的层序遍历/**转载请说明出处与作者*作者:多巴胺dopamine*/一问题描述1题目给你二叉树的根节点root,返回其节点值的层序遍历。(即......
  • win32com:word操作之 通过文字查找段落
      练习:#遍历可以查找出所有包含关键字的段落#去掉遍历只查找到第一个包含关键字的段落fullrange=doc.Range()foriinrange(4):fullrange.Find.Execut......
  • 第6章 数组、排序和查找
    ​6.1 为什么需要数组Array     数组可以存放多个同一类型的数据,数组的数据类型是引用类型。6.2 数组的使用     ​​​​​​​1)使用方式1:动......
  • 2022-8-19 剑指offer-二叉树-递归
    剑指OfferII055.二叉搜索树迭代器难度中等30收藏分享切换为英文接收动态反馈实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代......
  • 二分查找的模板
    二分查找的难度不低:从定义上来看:为什么需要二分查找大神总结:[]:https://leetcode.cn/circle/article/xYBtLt/#迭代版模板......
  • 【LeetCode】101.对称二叉树
    【LeetCode】101.对称二叉树/* *转载请说明出处与作者*作者:多巴胺dopamine*/一问题描述1题目给你一个二叉树的根节点root,检查它是否轴对称。示例1:输......