leetCode(46):Kth Smallest Element in a BST
2024-10-01 12:43:46
Given a binary search tree, write a function kthSmallest
to find the kth
smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
直观地一想。查找第k小的数,不就是遍历到第k个数吗?所以中序遍历非常easy想到,例如以下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> nodeStack;
TreeNode* tmp=root;
int kthMin = 0;
int kthValue;
while ((!nodeStack.empty() || tmp!=NULL) && kthMin!=k)
{
while (tmp != NULL)
{
nodeStack.push(tmp);
tmp = tmp->left;
}
tmp = nodeStack.top();
nodeStack.pop();
kthMin++;//对中序遍历稍加改动
kthValue = tmp->val;
tmp = tmp->right;
}
return kthValue;
}
};
另外。看了一下网友的解答,很巧妙。
他是先统计左子树上节点个数,假设节点个数小于k。则在右子树上找第k-n-1小的数,假设刚为k则就是当前节点,假设大于k,则继续在左子树上找第k小的数。
只是。每次递归都要统计一次节点个数,会不会导致复杂度添加?
int kthSmallest(TreeNode* root, int k) {
if (!root) return 0;
if (k==0) return root->val; int n=count_size(root->left);
if (k==n+1) return root->val; if (n>=k){
return kthSmallest(root->left, k);
}
if (n<k){
return kthSmallest(root->right, k-n-1);
} } int count_size(TreeNode* root){
if (!root) return 0;
return 1+count_size(root->left)+count_size(root->right); }
最新文章
- C#调用百度静态地图
- Marshal
- Android IntentService完全解析 当Service遇到Handler
- PHP 错误与异常 笔记与总结(18 )页面重定向实现
- C#中的WebBrowser控件加载ActiveX插件
- Codeforces 383C . Propagating tree【树阵,dfs】
- MySQL性能优化方案
- 【技巧】datagrid锁定列后重新加载时出现错位问题的解决
- Spring异常处理@ExceptionHandler
- 理解block和inode
- 配置JDK和Tomcat环境变量
- TensorFlow深度学习入门
- Python3基础 函数 未指定返回值,返回NONE
- day103 跨域请求 与频率访问限制.
- [转] Linux Crontab 定时任务 命令详解
- spring怎么实现单例模式?
- SQL操作语句之查询及删除重复记录的方法
- 八、Node.js-http模块
- float/文档流
- Oracle审计--AUD$占用空间较大处理方案