设为首页 加入收藏

TOP

剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小于根,右边的元素大于根】
2019-09-04 01:01:35 】 浏览:29
Tags:剑指 offer62 搜索 结点 左边 元素 于根 右边

1 题目描述

  给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)? ? 中,按结点数值大小顺序第三小结点的值为4。

2 思路和方法

  二叉搜索树【左边的元素小于根,右边的元素大于根】,按照中序遍历的顺序打印出来正好就是排序好的顺序。?中序遍历这颗二叉树,然后设置一个变量,访问一个变量的时候就加一,判断这个变量和k是否相等,如果相等,则将当前的这个结点返回即可

3 C++核心代码

 1 class Solution {
 2 public:
 3     TreeNode* KthNode(TreeNode* pRoot, int k) {
 4         if (k < 0 || pRoot == nullptr) {
 5             return nullptr;
 6         }
 7         N = k;
 8         InOrder (pRoot);
 9         return res;
10     }
11     void InOrder (TreeNode* r) {
12         if (r == nullptr || tag) {
13             return;
14         }
15         InOrder (r->left);
16         ++n;
17         if (n == N) {
18             res = r;
19             tag = true;
20             return;
21         }
22         InOrder (r->right);
23     }
24     
25     int N {0};
26     int n {0};
27     bool tag {false};  // 找到的标记,提前结束没必要的搜索
28     TreeNode* res {nullptr};
29 };
View Code

参考资料

https://blog.csdn.net/qq_35976351/article/details/88619952


剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小于根,右边的元素大于根】 https://www.cppentry.com/bencandy.php?fid=49&id=250076

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇洛谷 P1004 方格取数 下一篇C++基础--引用

kafka-
kafka ? Partit
解决android studio
Kafka史上最详细原理
Error while fetchin
【Kafka】安装与快速
? ? &
flume读取日志数据写
Authentication plug
Flume 自定义source
flume ? 三大核
ICC副本>>>
愚公移山 ?
Hbase架构 ? Hb
5 hbase-shell + &
Hbase ? MapRed
MetaException(messa
Exception in thread
HIVE metastore Dupl
-->