代码随想录算法训练营day21|530.二叉搜索树的最小绝对值差、501.二叉搜索树中的众数、236.二叉树的最近公共祖先

本文主要是介绍代码随想录算法训练营day21|530.二叉搜索树的最小绝对值差、501.二叉搜索树中的众数、236.二叉树的最近公共祖先,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉搜索树的最小绝对值差

递归法        

        首先需考虑这是一个二叉搜索树,在中序遍历后的结果为从小到大的一个序列,寻找二叉搜索树的最小绝对值差,只需比较一个节点与之后的差值即可。在遍历的过程中,我们需要一个节点保存前节点,之后计算前节点和当前节点的差值,将所有节点都遍历一遍后即可得到二叉搜索树的最小绝对值差。

class Solution {
public:// 用于存储最小差值的变量,初始值设为最大整数,以便后续比较int minDiff = INT_MAX;// 用于记录前一个节点的指针,初始值为nullptrTreeNode *pre = nullptr;// 中序遍历二叉树的递归函数void inorder_traversal(TreeNode* root, TreeNode*& pre, int& minDiff) {// 如果当前节点为空,则返回if(root == nullptr){return;}// 首先递归遍历左子树inorder_traversal(root->left, pre, minDiff);// 如果前一个节点不为空,则计算当前节点和前一个节点的差值,并更新最小差值if(pre != nullptr){minDiff = std::min(minDiff, root->val - pre->val);}// 将当前节点设置为前一个节点,以便下一次比较pre = root;// 最后递归遍历右子树inorder_traversal(root->right, pre, minDiff);}// 主函数,调用中序遍历函数并返回最小差值int getMinimumDifference(TreeNode* root) {TreeNode* pre = nullptr; // 前一个节点的指针int minDiff = INT_MAX;  // 最小差值// 调用中序遍历函数inorder_traversal(root, pre, minDiff);// 返回最小差值return minDiff;}
};

算法的时间复杂度和空间复杂度为O(n)。

二叉搜索树中的众数

递归+哈希表

        由于要遍历所有的节点,最简单的方法,创建一个哈希表,将所有的节点出现次数加入哈希表,最后将哈希表中出现次数最多的数全部返回。

class Solution {
public://前序遍历void preorder_traversal(TreeNode* root, unordered_map<int, int>& umap) {if (root == nullptr) {return;}umap[root->val] += 1; // 统计当前节点值的出现次数preorder_traversal(root->left, umap); preorder_traversal(root->right, umap);}vector<int> findMode(TreeNode* root) {int max_value = 0; // 用于存储最大出现次数vector<int> ans; // 用于存储众数unordered_map<int, int> umap; // 用于存储每个值及其出现次数preorder_traversal(root, umap); // 调用前序遍历函数// 遍历哈希表,找到出现次数最多的值for (const auto& pair : umap) {if (pair.second > max_value) {max_value = pair.second; // 更新最大出现次数ans.clear(); // 清空之前的众数ans.push_back(pair.first); // 添加新的众数} else if (pair.second == max_value) {ans.push_back(pair.first); // 如果有多个出现次数相同的值,都添加到众数列表中}}return ans; // 返回众数列表}
};

分析代码的时间复杂度和空间复杂度。

在时间复杂度上,遍历树的每一节点,时间复杂度为O(n),此外,在寻找众数时,需要遍历哈希表,同样需要O(n),综上,时间复杂度为O(n)。

空间复杂度,哈希表存储了树中所有不同值的出现次数,最差情况为O(n),此外,递归调用栈的空间复杂度为O(H),H为树的高度,最差情况下为O(n)。因此最终时间复杂度和空间复杂度均为O(n)。

双指针

二叉搜索树,一定得是中序遍历,中序遍历结果的序列才是有序的。

定义一个全局变量max_count,一个count,在函数体创建一个ans数组,在中序遍历时,参考上题,设定一个pre指针,指向当前的前一个位置,当现在位置的val与pre->val相同时,count++,遍历第一次的count更新max_count,并将值加入ans数组,之后的遍历结果若count大于max_count,则更新max_count,并将ans数组清空,并将val值存入数组,若count等于max_count,则在ans数组中加入val。遍历一次之后即能得到所有众数。

class Solution {
public:int max_count = 0;int count = 1;TreeNode*pre = nullptr;void inorder_traversal(TreeNode* root,vector<int>&ans){if(root == nullptr){return;}inorder_traversal(root->left,ans);if(pre != nullptr){if(root->val == pre->val){count++;}else{count = 1;}}if(count > max_count){max_count = count;ans.clear();ans.push_back(root->val);}else if(count == max_count){ans.push_back(root->val);}pre = root;inorder_traversal(root->right,ans);}vector<int> findMode(TreeNode* root) {vector<int>ans;inorder_traversal(root,ans);return ans;}
};

算法的时间复杂度和空间复杂度均为O(n)。

二叉树的最近公共祖先

递归法

由于是要寻找最近的公共祖先,我们得考虑从叶子节点向上递归,因此考虑后序遍历的方式,左右中,从底部向上找。

具体参考代码随想录讲解视频。

自底向上查找,有点难度! | LeetCode:236. 二叉树的最近公共祖先_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1jd4y1B7E2/?spm_id_from=333.788&vd_source=fc4a6e70e3a87b7ea67c2024e326e7c5

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点为空,或者等于p或q,直接返回当前节点if (root == nullptr || root == p || root == q) {return root;}// 在左右子树中递归寻找p和qTreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果左右子树的返回值都不为空,说明当前节点就是最近公共祖先if (left != nullptr && right != nullptr) {return root;}// 否则,返回非空的子树返回值return left != nullptr ? left : right;}
};

算法的时间复杂度和空间复杂度均为O(n)

这篇关于代码随想录算法训练营day21|530.二叉搜索树的最小绝对值差、501.二叉搜索树中的众数、236.二叉树的最近公共祖先的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1011683

相关文章

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架,使用的是

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》:本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝?ArrayList 浅拷贝的重要性方法一:使用构造函数方法二:使用 addAll(