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

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

智能推荐

form表单提交的几种方式_提交表单-程序员宅基地

文章浏览阅读10w+次，点赞92次，收藏495次。表单提交方式一：直接利用form表单提交html页面代码：<!DOCTYPE html><html><head><meta charset="UTF-8" /><title>Insert title here</title></head><body><form action="h..._提交表单

Unity Spine SkeletonGraphic 动画重复播放过度残影透明渐变Bug 解决方案_unity skeletongraphic-程序员宅基地

文章浏览阅读5.1k次。Unity Spine SkeletonGraphic 重复播放过度残影Bug 解决方案不推荐使用SetToSetupPose和Setup Pose相关，代码直接贴上/// <summary>/// Spine播放设置/// </summary>/// <param name="trackIndex">填写0</param>/// <param name="animationName">动画名</param>/// &l_unity skeletongraphic

高斯分布3——边缘概率与条件概率_高斯分布的条件概率-程序员宅基地

文章浏览阅读3.5k次。一、推导过程:二、结果：边缘分布x1,x2 各自依然服从 μi，写反差矩阵 Σii 的多元高斯分布；条件概率分布给定 xj 求 xi 的分布：μi|j=μi+ΣijΣ−1jj(xj−μj)Σi|j=Σjj−ΣTijΣ−1iiΣij..._高斯分布的条件概率

Ratelimitcache: Python缓存库，支持速率限制-程序员宅基地

文章浏览阅读339次，点赞8次，收藏8次。Ratelimitcache: Python缓存库，支持速率限制项目链接: https://gitcode.com/simonw/ratelimitcache?utm_source=artical_gitcode如果你正在寻找一个Python缓存库，并且希望对缓存操作进行速率限制，那么Ratelimitcache可能是你的理想选择。什么是Ratelimitcache？Ratelimitca..._python ratelimit基于什么

【爬虫】Xpath和CSS信息提取的方法异同点_xpath 获取css-程序员宅基地

文章浏览阅读2.3k次，点赞2次，收藏8次。Xpath和CSS信息提取的方法异同点_xpath 获取css

随便推点

基于OFDM+64QAM系统的载波同步matlab仿真,输出误码率,星座图,鉴相器,锁相环频率响应以及NCO等-程序员宅基地

文章浏览阅读454次。正交频分复用（OFDM）是一种在现代通信系统中广泛使用的调制技术，它具有高效的频谱利用和抗多径衰落等特点。64QAM（64-ary Quadrature Amplitude Modulation）是一种调制方式，可以在每个符号中传输更多的位信息。在OFDM系统中，保持载波同步对确保数据传输的可靠性至关重要。_基于ofdm+64qam系统的载波同步matlab仿真,

Springboot毕设项目超市商品销售管理系统37x2w（java+VUE+Mybatis+Maven+Mysql）_vue+springboot+mybatis商品管理系统-程序员宅基地

文章浏览阅读67次。Jdk1.8 + Tomcat8.5 + Mysql + HBuilderX（Webstorm也行）+ Eclispe（IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持）。若包含，则为maven项目，否则为非maven项目。Springboot毕设项目超市商品销售管理系统37x2w（java+VUE+Mybatis+Maven+Mysql）Springboot + mybatis + Maven + Vue 等等组成，B/S模式 + Maven管理等等。其他版本理论上也可以。_vue+springboot+mybatis商品管理系统