剑指Offer(六十二):二叉搜索树的第k个结点

2018年1月31日09:55:02 7 588 °C
摘要

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

剑指Offer(六十二):二叉搜索树的第k个结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

给定一颗二叉搜索树,请找出其中的第k大的结点。例如,在下图中,按结点数值大小顺序第三个结点的值为4。

剑指Offer(六十二):二叉搜索树的第k个结点

这棵树是二叉搜索树,首先想到的是二叉搜索树的一个特点:左子结点的值 < 根结点的值 < 右子结点的值。

1、思路

如上图所示,如果使用终须遍历,则得到的序列式为{2,3,4,5,6,7,8}。因此,只需要用中序遍历一棵二叉搜索树,就很容易找出它的第k大结点。

2、代码

C++:

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:7   其中:访客  4   博主  3

    • avatar 卷卷 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学六舍东(研究生) 3

      我觉得二叉树又难又简单。。。。

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

          @卷卷 you need 手把手教学。

        • avatar 大敏 来自天朝的朋友 谷歌浏览器  LLD-AL10 Build/HONORLLD-AL10 广东省深圳市 联通 1

          大神,18行的调用,与21行的定义,参数k不一样呢?

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

              @大敏 哪里不一样?一样的吧。

            • avatar 大敏 来自天朝的朋友 谷歌浏览器 Windows 7 广东省深圳市罗湖区 电信 2

              大神,我仔细看了一下,k如果是各个递归中都要用到的话,应该传指针才对;如果那样的话,29,32行应该是对*k进行判断和操作才对吧

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                  @大敏 哦,你是说这个k这里啊,这个用引用和指针都是可以的,两种操作方法而已。

                    • avatar 大敏 来自天朝的朋友 谷歌浏览器  LLD-AL10 Build/HONORLLD-AL10 广东省深圳市罗湖区 电信 1

                      @Jack Cui 原来是引用,我没有使用过引用,大神提醒才想起,感谢感谢