C++二叉搜索树中第K小的元素

简介: C++二叉搜索树中第K小的元素

C++二叉搜索树中第K小的元素

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言


230. 二叉搜索树中第K小的元素 - 力扣(LeetCode)

题目描述

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

解题思路

我们采用中序遍历+计数器剪枝的思路

算法流程:

1.定义⼀个全局的变量count,在主函数中初始化为k的值(不⽤全局也可以,当成参数传⼊递归过

程中);

递归函数的设计:void dfs(TreeNode* root):

  • 返回值为第k个节点;

递归函数流程(中序遍历):

  1. 递归出⼝:空节点和count == 0直接返回,说明没有找到;
  2. 去左⼦树上查找结果 dfs(root->left);
  3. 判断是否找到了第k个节点:
count--;
        if(count == 0) ret = root->val;
  1. 去右⼦树上查找结果 dfs(root->right);

代码:

class Solution {
    int count = 0;
    int ret = 0;
public:
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        return ret; 
    }
    void dfs(TreeNode* root)
    {
        //截止条件
        if(root == nullptr ||count == 0) return;
        //中序遍历
        dfs(root->left);
        count--;
        if(count == 0) ret = root->val;
        dfs(root->right);
    }
};

总结

我们采用了全局变量count和ret+剪枝的两种优化方式来进行优化我们dfs二叉树的过程,提高了代码运行的效率。

相关文章
|
2月前
|
搜索推荐 编译器 C语言
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
78 4
|
6月前
|
算法 测试技术 C++
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
|
6月前
|
C++ 容器
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
|
4月前
|
存储 C++
【C++】二叉树进阶之二叉搜索树(下)
【C++】二叉树进阶之二叉搜索树(下)
32 4
|
4月前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树(上)
【C++】二叉树进阶之二叉搜索树(上)
36 3
|
4月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
35 2
|
5月前
|
存储 C++
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
35 1
|
5月前
|
C++
C++数组中插入元素。
C++数组中插入元素。
|
4月前
|
安全 编译器 C++
【C++】string类的使用②(元素获取Element access)
```markdown 探索C++ `string`方法:`clear()`保持容量不变使字符串变空;`empty()`检查长度是否为0;C++11的`shrink_to_fit()`尝试减少容量。`operator[]`和`at()`安全访问元素,越界时`at()`抛异常。`back()`和`front()`分别访问首尾元素。了解这些,轻松操作字符串!💡 ```
|
6月前
|
存储 C语言 Python
从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题(下)
从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题
74 3