个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
注意:这道题目涉及到二叉搜索树的内容 ,若有不懂的可以参考下面这篇文章?
题目链接:二叉搜索树中第K小的元素
题目
给定一个二叉搜索树的根节点?root
?,和一个整数?k
?,请你设计一个算法查找其中第?k
?个最小元素(从 1 开始计数)。
示例 1:
输入:root = [3,1,4,null,2], k = 1 输出:1
示例 2:
输入:root = [5,3,6,2,4,null,null,1], k = 3 输出:3
提示:
n
?。1 <= k <= n <= 104
0 <= Node.val <= 104
进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第?k
?小的值,你将如何优化算法?
题目意思很简单,给我们一颗二叉搜索树,我们找出第 k 个最小的值(从 1 开始)
二叉搜索树有如下特性:
解法一:
依靠二叉搜索树的特性:中序遍历为有序
思路:创建一个全局变量 v ,中序遍历整个二叉树,将搜索二叉树的值存入 v 中,然后再返回 v[k-1] 即可
解法二:
解法一虽然也可以通过,上述解法不仅使??量额外空间存储数据,并且会将所有的结点都遍历?遍。 我们没有必要遍历整个二叉搜索树。
void?dfs(TreeNode* root);
以上思路就讲解完了,大家可以先自己先做一下?
解法一
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
vector<int> v;
void dfs(TreeNode* root)
{
if (root == nullptr)
{
return;
}
dfs(root->left);
v.push_back(root->val);
dfs(root->right);
}
int kthSmallest(TreeNode* root, int k)
{
dfs(root);
return v[k-1];
}
};
解法二
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int count;
int ret;
void dfs(TreeNode* root)
{
if(root == nullptr || count == 0) return;
dfs(root->left);
count--;
if(count == 0) ret = root->val;
dfs(root->right);
}
int kthSmallest(TreeNode* root, int k)
{
count = k;
dfs(root);
return ret;
}
};