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

  • A+
所属分类:剑指Offer
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

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

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

1、思路

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

2、代码

C++:

Jack Cui

发表评论

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