leetcode 剑指 Offer 54. 二叉搜索树的第k大节点_leetcode 二叉搜索树的第k大节点-程序员宅基地

技术标签：剑指offer

文章目录

题目要求

给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路

利用性质迭代

利用性质：二叉搜索树的中序遍历是递减的，因此二叉搜索树中序遍历的倒序是递增的。

二叉树的中序遍历：

recursive(root.left)
print(root.val)
recursive(root.right)

此外：

每当遍历到root的时候，k要减1。
k == 0时，将root.val作为结果存储。
k == 0时，停止迭代。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def kthLargest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        def recursive(root):
            # 若根节点为空，则停止本次迭代。
            if not root:
                return
            # 先右节点。
            recursive(root.right)
            # 若self.k等于0，则提前终止迭代。
            if self.k <= 0:
                return
            # 到root节点时，执行k减1的操作，且当self.k为0时，证明找到第k大的数了，记录之。
            self.k -= 1
            if self.k == 0:
                self.res =  root.val
            # 再左节点。
            recursive(root.left)

        self.k = k
        recursive(root)

        return self.res

知识点

python类中的__init__，是每次Class被实例化就会自动执行一次。
self.name可以在类内被任意调用。本题中的，self.k和self.res也是如此。

本文链接：https://blog.csdn.net/qq_40317204/article/details/114539257

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

开源项目，毕业设计_本科毕业设计拿别人的开源代码修改-程序员宅基地

文章浏览阅读1.5w次，点赞35次，收藏385次。自己在网上找的开源项目，比较好分享给大家热门开源项目（包含小四轴、智能手环、光立方、智能车、防丢器等项目）号外！号外！（搞四轴，有这套就足够了！)科研级别的小四轴STM32F4芯片支持WIFI且android手机控制自适应控制就是牛掰！该飞机面向有科研和强烈学习意向的小伙伴们使用，如果只是想玩的话你肯定不会喜欢这套四轴的，主要设计思想是提供一个高性能的控制和姿态算法验证平台，因此..._本科毕业设计拿别人的开源代码修改

Java快速开发框架_若依——Ruoyi添加自己的业务模块_ruoyi java17-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏26次。QQ 1274510382Wechat JNZ_aming商业联盟 QQ群538250800技术搞事 QQ群599020441解决方案 QQ群152889761加入我们 QQ群649347320共享学习 QQ群674240731纪年科技aming网络安全 ,深度学习,嵌入式,机器强化,生物智能,生命科学。叮叮叮：产品已上线 —>关注官方-微信公众号——济南纪年信息科技有限公司民生项目：商城加盟/娱乐交友/创业商圈/外包兼职开发-项目发布/安全项目：态势感.._ruoyi java17

CISCO 交换机配置 Web浏览器的方式-程序员宅基地

文章浏览阅读9k次，点赞2次，收藏3次。　当利用Console口为交换机设置好IP地址信息并启用HTTP服务后，即可通过支持JAVA的Web浏览器访问交换机，并可通过Web通过浏览器修改交换机的各种参数并对交换机进行管理。事实上，通过Web界面，可以对交换机的许多重要参数进行修改和设置，并可实时查看交换机的运行状态。不过在利用 Web浏览器访问交换机之前，应当确认已经做好以下准备工作：·在用于管理的计算机中安装T..._思科交换机2960s有web配置吗

ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:22122, response status 2 != 0-程序员宅基地

文章浏览阅读2.5w次，点赞2次，收藏6次。报错信息： [2018-09-09 20:33:12] ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:22122, response status 2 != 0 [2018-09-09 20:33:12] ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:..._error - file: tracker_proto.c, line: 48, server: 172.17.0.1:22122, response

使用matplotlib显示图片（《深度学习入门：基于Python的理论与实现》实践笔记）_matplotlib展示图片-程序员宅基地

文章浏览阅读3.9k次。使用matplotlib显示图片（《深度学习入门：基于Python的理论与实现》实践笔记）一、安装matplotlib库二、导入matplotlib.pyplot库和matplotlib.image库里的imread函数三、实例：显示图片一、安装matplotlib库在命令行使用下面的命令即可：pip install matplotlib二、导入matplotlib.pyplot库和matplotlib.image库里的imread函数在程序开头使用：import matplotlib.pyp_matplotlib展示图片

Subversion实践案例——客户现场模式的分布式开发_开发去客户现场的案例-程序员宅基地

文章浏览阅读1.2k次。基本信息用户单位：某应用软件研发企业用户规模：100人以上组织过程水平：中等 CMMI评审等级：无 Subversion使用时间：1年客户需求由于公司每次向新客户提交软件的时候都需要派出一个小规模的团队到客户现场进行一段时间的软件定制和维护。此外，老客户系统的重大升级和功能扩展也需要一个小团队在客户现场进行一段时间的开发。因此，异地开发的配置管理就是一_开发去客户现场的案例

随便推点

（基于matlab自写代码）语音信号的短时分析，计算平均能量，短时过零数_matlab求语音信号短时过零率的函数-程序员宅基地

文章浏览阅读3.2k次。一定时宽的语音信号，其能量的大小随时间有明显的变化。清音段能量比浊音段小得多。短时过零数也可用于语音信号分析中，发浊音时，其语音能量约集中于3kHz以下，而发清音时，多数能量出现在较高频率上。可认为浊音时具有较低的平均过零数，而清音时具有较高的平均过零数，故对一短时语音段计算其短时平均能量及短时平均过零数，就可以区分其中的清音段和浊音段，从而可判别句中清、浊音转变时刻，声母韵母的分界以及无声与有声的分界。这在语音识别中有重要意义。自己编写的matlab代码，对一段语音，取帧长为240个点，计算其平均能_matlab求语音信号短时过零率的函数