剑指offer 面试题. 二叉搜索树的第k个结点
2024-09-06 03:14:10
题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
解:
由于二叉搜索树的中序遍历是升序,所以在中序基础上添加计数器即可。
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
int i=INT32_MIN;
return func(pRoot,k,i);
}
TreeNode* func(TreeNode* node,int k,int& i){
if(node==nullptr){
if(i==INT32_MIN){
i=;
}
return nullptr;
}
decltype(node) t;
if(t=func(node->left,k,i)){
return t;
}
++i;
if(i==k){
return node;
}
if(t=func(node->right,k,i)){
return t;
}
return nullptr;
}
};
最新文章
- 【验证】C# dataSource 的记忆功能
- Boost 安装
- CF 204B Little Elephant and Cards
- Using Post_Query Trigger in Oracle Forms
- canvas绘图动画细节
- oracle12c不能进入到http://localhost:5500/em的解决办法
- Linux网络编程7——使用TCP实现双方聊天
- java 开发环境
- 惊艳的随机化方法 -World Search (homework-04)
- Hibernate一 入门
- (推荐)jquery.pagination.js分页
- WDLINUX (Centos5.8) 安装 soap
- [leetcode-556-Next Greater Element III]
- 我的Spring学习记录(四)
- eclipse工作空间的基本配置
- 学习easyui的小伙伴有福利了
- makefile $@, $^, $<;, $? 表示的意义
- 2018-2019-2 《网络对抗技术》Exp3 免杀原理与实践 20165215
- day-02
- Confluence 6 数据库和临时目录