61二叉搜索树的第k个结点
2024-09-04 19:05:58
题目描述
给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。
思路:二叉搜索树的中序遍历是递增的序列,使用循环的中序遍历找到第k个节点就行了,对中序遍历的循环版本没理解,使用一个stack,找到最左边的节点,所以初始化的时候首先初始化节点,stack要为空。计数的cnt要初始化为0。不清楚的话就一个节点的时候判断一下,然后p = p->right,不需要判断为空,因为为空的话,上面的循环不会进入。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k){
if(pRoot == nullptr){
return nullptr;
}
stack<TreeNode*> s;
//s.push(pRoot);
TreeNode* p = pRoot;
int cnt = ;
while(!s.empty() || p != nullptr){
while(p != nullptr){
s.push(p);
p = p->left; }
if(!s.empty()){
p = s.top();
s.pop();
++cnt;
if(cnt == k){
return p;
}
p = p->right;
}
}
return nullptr;
}
};
最新文章
- Assertor用于判断参数和抛出异常
- springMVC含文件上传调用ajax无法连接后台
- xss如何加载远程js的一些tips
- Careercup - Google面试题 - 5634470967246848
- toB的产品经理和toc产品经理区别
- MAC 终端 显示隐藏文件 关闭显示隐藏文件
- Cracking the coding interview--Q2.4
- Fedora 问题总结第二季
- javascript 之作用域-06
- js 时间戳 vue 时间戳的转换 ?
- 恶补web之二:css知识(2)
- lookup_peer.go
- 如何使用Keras的Model visualization功能
- [IOI2000] 邮局
- hue报错StructuredException: timed out (code THRIFTSOCKET): None的处理
- 微软BI 之SSIS 系列 - 导出数据到 Excel 2013 的实现
- ms sql server,oracle数据库实现拼接一列的多行内容
- opencv学习之路(5)、鼠标和滑动条操作
- Android NDK r9的配置与使用
- BitSet 是个好东西