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二叉树的过程,提高了代码运行的效率。

目录
打赏
0
0
0
0
0
分享
相关文章
|
1月前
|
c++ 红黑树(自平衡二叉搜索树)(k,v型)
因为红黑树是一种特殊的AVL树(但少了平衡因子的存在),所以其结点的定义是在AVL树上加上新的成员变量,用于表示结点的颜色。RED,BLACK,//三叉链, _kv(kv){}首先我们在默认构造上,默认构造结点的颜色默认情况下为红色所以为什么构造结点时,默认将结点的颜色设置为红色?这是因为:当我们向红黑树插入结点时,若我们插入的是黑色结点,那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个,即破坏了红黑树的性质4,此时我们就需要对红黑树进行调整。
65 0
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
171 4
|
8月前
|
【C++】二叉搜索树(BST)
二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,其每个节点的左子树所有节点值小于该节点值,右子树所有节点值大于该节点值,且左右子树也均为二叉搜索树。BST支持高效的数据查找、插入和删除操作,时间复杂度通常为O(log n)。本文档详细介绍了BST的基本概念、存储结构及其实现,包括迭代和递归两种方式的查找、插入、删除等操作的具体代码示例。
136 3
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
【C++】二叉树进阶之二叉搜索树(下)
【C++】二叉树进阶之二叉搜索树(下)
68 4
【C++】二叉树进阶之二叉搜索树(上)
【C++】二叉树进阶之二叉搜索树(上)
63 3
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
82 2
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
63 1
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问