跟着姚桑学算法-二叉搜索树的第k个结点

简介: 剑指offer算法

题. 二叉搜索树的第k个结点

给定一棵二叉搜索树,请找出其中的第 k 小的结点。

你可以假设树和 k 都存在,并且 1≤k≤ 树的总结点数。

数据范围
树中节点数量 [1,500]。

样例

输入:root = [2, 1, 3, null, null, null, null] ,k = 3

    2
   / \
  1   3

输出:3

【题解】--- 递归剪枝

简单地说,就是如果在函数中存在着调用函数本身的情况,这种现象就叫 递归

以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用,所以此函数是递归函数

publicintfactorial(int n){if (n < =1) {return1; }return n * factorial(n - 1)}

进一步剖析「递归」,先有「递」再有「归」,「递」的意思是将问题拆解成子问题来解决, 子问题再拆解成子子问题,...,直到被拆解的子问题无需再拆分成更细的子问题(即可以求解),「归」是说最小的子问题解决了,那么它的上一层子问题也就解决了,上一层的子问题解决了,上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象,那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

注意:

  • 递归一定要有条件限定,保证递归能够停止下来,否则会发生栈内存溢出。
  • 在递归中虽然有限定条件,但是递归次数不能太多。否则也会发生栈内存溢出。
  • 构造方法,禁止递归

方法一:dfs(TreeNode* root, int& k)中把k作为参数传入同时加上引用&,相当于全局变量;

方法二:把k作为全局变量,就不用dfs递归的时候把k做参数传入同时加引用&,会更容易理解;

具体实现见代码注释。

复杂度分析:

时间复杂度为O(logn)。

C++代码实现:

// 方法一:dfs(TreeNode* root, int& k)中把k作为参数传入 同时加上引用&,相当于全局变量
// 中序遍历,看清 第k大还是第k小,第k大是 右中左,第k小是 左中右
class Solution {
public:
    int ans;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }

    // 这里需要保证所有dfs函数共用一个k,加引用之后 k就相当于全局变量了
    void dfs(TreeNode* root, int& k){ // dfs函数返回值为void, 参数k要加引用&
        if (!root) return; // 搜索到叶子结点就返回
        dfs(root->right, k);           // 右
        if (k == 0) return;   // 利用k值进行剪枝
        if (--k == 0){                // 中
            ans = root->val;
            return;           // 剪枝
        }
        dfs(root->left, k);            // 左
    }
};

// 方法二:把k作为全局变量,就不用dfs递归的时候把k做参数传入同时加引用&,更好理解
class Solution {
public:
    int k, ans; //注意这里直接把 k 转变为全局变量,否则就要 在dfs(TreeNode* root, int& k)中把k作为参数传入 同时加上引用&
    int kthLargest(TreeNode* root, int _k) {
        k = _k;  // k 转化为全局变量
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root){
        if (!root) return; // 搜索到叶子结点就返回
        dfs(root->right);             // 右
        if (k == 0) return;   // 利用k值进行剪枝
        if (--k == 0){                // 中
            ans = root->val;
            return;           // 剪枝
        }
        dfs(root->left);             // 左
    }
};
目录
相关文章
|
8月前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
5月前
|
存储 监控 算法
公司内部网络监控中的二叉搜索树算法:基于 Node.js 的实时设备状态管理
在数字化办公生态系统中,公司内部网络监控已成为企业信息安全管理体系的核心构成要素。随着局域网内终端设备数量呈指数级增长,实现设备状态的实时追踪与异常节点的快速定位,已成为亟待解决的关键技术难题。传统线性数据结构在处理动态更新的设备信息时,存在检索效率低下的固有缺陷;而树形数据结构因其天然的分层特性与高效的检索机制,逐渐成为网络监控领域的研究热点。本文以二叉搜索树(Binary Search Tree, BST)作为研究对象,系统探讨其在公司内部网络监控场景中的应用机制,并基于 Node.js 平台构建一套具备实时更新与快速查询功能的设备状态管理算法框架。
138 3
|
12月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
182 1
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
195 22
|
7月前
|
存储 监控 算法
基于 PHP 二叉搜索树算法的内网行为管理机制探究
在当今数字化网络环境中,内网行为管理对于企业网络安全及高效运营具有至关重要的意义。它涵盖对企业内部网络中各类行为的监测、分析与管控。在内网行为管理技术体系里,算法与数据结构扮演着核心角色。本文将深入探究 PHP 语言中的二叉搜索树算法于内网行为管理中的应用。
69 4
|
8月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
8月前
|
监控 算法 安全
关于公司电脑桌面监控中 PHP 二叉搜索树算法的深度剖析
在现代企业管理中,公司电脑桌面监控系统通过二叉搜索树(BST)算法保障信息安全和提高效率。本文探讨PHP中的BST在监控场景的应用,包括节点定义、插入与查找操作,并展示如何管理时间戳数据,以快速查询特定时间段内的操作记录。BST的高效性使其成为处理复杂监控数据的理想选择。
65 2
|
9月前
|
存储 算法 安全
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
96 3
|
存储 算法 C#
C#二叉搜索树算法
C#二叉搜索树算法
|
算法 安全 数据库
基于结点电压法的配电网状态估计算法matlab仿真
**摘要** 该程序实现了基于结点电压法的配电网状态估计算法,旨在提升数据的准确性和可靠性。在MATLAB2022a中运行,显示了状态估计过程中的电压和相位估计值,以及误差随迭代变化的图表。算法通过迭代计算雅可比矩阵,结合基尔霍夫定律解决线性方程组,估算网络节点电压。状态估计过程中应用了高斯-牛顿或莱文贝格-马夸尔特法,处理量测数据并考虑约束条件,以提高估计精度。程序结果以图形形式展示电压幅值和角度估计的比较,以及估计误差的演变,体现了算法在处理配电网状态估计问题的有效性。

热门文章

最新文章