leetcode 剑指 Offer 54. 二叉搜索树的第k大节点_条件反射104的博客-程序员宝宝

技术标签: 剑指offer  

题目要求

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

解题思路

利用性质迭代

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

二叉树的中序遍历:

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

此外:

  1. 每当遍历到root的时候,k要减1。
  2. k == 0时,将root.val作为结果存储。
  3. 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

知识点

  1. python类中的__init__,是每次Class被实例化就会自动执行一次。
  2. self.name可以在类内被任意调用。本题中的,self.k和self.res也是如此。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_40317204/article/details/114539257

智能推荐

electron-vue pdf在线预览!_sisyphus0000的博客-程序员宝宝_electron pdf预览

气死我了,用了好几种方法,但是文字就是缺失,但是pdf.js没使用啊,各位大佬有啥好方法,你们尽情用,我针对的是electron的我新开了窗口,用了electron-pdf-window这个插件npm i electron-pdf-window然后页面引入const { BrowserWindow } = require("electron").remote;const PDFWindow = require("electron-pdf-window");最后在要预览的pdf的.

简单理解:第一类错误,第二类错误,统计显著性,空假设和P值_粥小文的博客-程序员宝宝_第一类错误

目录第一类错误(Type I error)第二类错误(Type II error)统计显著性( Statistical significance)空假设H0(Null hypothesis)P值(p value)参考第一类错误(Type I error)第一类错误,就是我们所说的假阳性结论(FP, False Positive)。例如,统计测试说路人甲有新冠,它很危险,但实际上它没有,只是发烧了,这就是一个FP。第二类错误(Type II error)第二类错误,就是我们所说的假阴性结论(FN, F

2.5判断测试fxblue跟单ea是否正确安装运行_量化研究所的博客-程序员宝宝

以下屏幕截图是fxblue喊单ea和fxblue跟单ea成功运行的示例:​如图所示,自动交易按钮要是按下去的播放键状态,Chaennl参数是一样的,Heartbeat sent后对应的时间也是同步的,代表fxbule跟单系统已经开始运作。正确跟单的三个关键点:1,dll文件是否正确安装,mt4设置里是否将“允许动态连接库”打“√”(95%网友在咨询我时都是此原因)2,Channel频道参数是否一致3,自动交易按钮是否已经开启为什么要用一个蓝色背景覆盖整个图表?相信有不少朋友有此疑问?其实,

utf-8的中文,一个字符占几个字节_kexiuyi的博客-程序员宝宝

from https://blog.csdn.net/kindsuper_liu/article/details/80202150英文字母和中文汉字在不同字符集编码下的字节数英文字母:·字节数 : 1;编码:GB2312字节数 : 1;编码:GBK字节数 : 1;编码:GB18030字节数 : 1;编码:ISO-8859-1字节数 : 1;编码:UTF-8字节数 :...

Win7下 OpenCV2.4.6 在VS2010上的安装_maochongsandai110的博客-程序员宝宝

参考网址:http://blog.csdn.net/zhangleicity/article/details/9907697  Win7 32位 VS2010 OpenCV 2.4.6 配置 http://www.cnblogs.com/freedomshe/archive/2012/04/25/2470540.html 安装步骤基本都相同,不同的是最后的链接器中依赖库文件会出

Flex mobile入门_iteye_15337的博客-程序员宝宝

Flex mobile入门 2010年12月17日  Adobe Flash Builder 4 简体中文正式版 Windows版点击下载:http://g.csdn.net/5134151   Adobe Flash Builder 4 简体中文正式版 Mac版点击下载:http://g.csdn.net/5134152   Adobe 在线课堂:http://adobev....

随便推点

源码剖析Yii错误 Invalid parameter number: no parameters were bound_SaneFuture的博客-程序员宝宝

Yii ActiveRecord使用的一个陷阱导致 Invalid parameter number: no parameters were bound请看下面的例子$criteria = new CDbCriteria();addInCondition$criteria=$this->getCommandBuilder()->createCriteria($condition,$params);

echarts legend不显示_ohmorning的博客-程序员宝宝_echarts legend不显示

1、情况一,要保证legend中的data与series中name相同,例如:var options = { legend:{ data:["2018","2019"] } series:[ { name:"2018", data:[10,20,30,40,50] }, { name:"2019", data:[30,60,70,60,80] } ]}myCharts.setOptions(options)2、情况二,如果legend中的data

Base64图片下载工具类_chao ge的博客-程序员宝宝

1、简介对base64编码字符串解码,还原成图片并保存到本地。2、工具类package com.company.project.common.utils;import sun.misc.BASE64Decoder;import java.io.FileOutputStream;import java.io.OutputStream;/** * @Description : // 对字节数组字符串进行Base64解码并生成图片 * @Author : Chaos * @Date :

全新出品!阿里 P5 工程师~P8 架构师晋升路线揭秘_Java烟雨的博客-程序员宝宝_架构师晋升路线

阿里巴巴终于公开了从初级程序员到架构师的学习路线图,这里相对应的基本上就是从P5到P8的晋升体系!今天老师将会带着大家从初级程序员开始一点点分享整个晋升体系!

【C】用迭代法求a^(1/2)。求平方根的迭代公式为x(n+1)=1/2*(x(n)+a/x(n)),_爱学习的小八的博客-程序员宝宝

//用迭代法求a^(1/2)。求平方根的迭代公式为x(n+1)=1/2*(x(n)+a/x(n)),要求前后两次求出的x的差的绝对值小于10^(-5)#include &lt;stdio.h&gt;#include &lt;math.h&gt;int main(){ int a; double x1,x2=1.0; scanf("%d",&amp;a); do{ x1=x2; x2=(x1+a/x1)/2; }while(fabs(x1-x2)&gt;=1e-5); printf