【算法训练 day23 二叉搜索树的最小绝对差、二叉搜索树的众数、二叉树的最近公共祖先】

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

目录

  • 一、二叉搜索树的最小绝对差-LeetCode 530
    • 思路
    • 实现代码
      • 递归处理
      • 使用数组
    • 个人问题
  • 二、二叉搜索树的众数-LeetCode 501
    • 思路
    • 实现代码
      • map统计计数
      • 递归过程中计数
    • 个人问题
  • 三.二叉树的最近公共祖先-LeeCode 236
    • 思路
    • 实现代码
    • 个人问题
    • 总结


一、二叉搜索树的最小绝对差-LeetCode 530

Leecode链接: leetcode 977
文章链接: 代码随想录
视频链接: B站

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

示例:

输入:root = [4,2,6,1,3]
输出:1

思路

解法1:转化为数组,然后逐个计算差值,返回最小差值即可。解法2:由于题目是搜索树,所以差值最小必定出现在相邻节点,使用全局变量保存上一个节点,中间节点计算差值并保存可能的最小差值。

实现代码

递归处理

//cpp
class Solution {
public:TreeNode* pre = nullptr;int minnum = INT32_MAX;void test(TreeNode* root){if(root == nullptr) return;test(root->left);if(pre != nullptr){minnum = min(minnum,root->val - pre->val);}pre = root;test(root->right);}int getMinimumDifference(TreeNode* root) {test(root);return minnum;}
};

使用数组

//cpp
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);
}
public:int getMinimumDifference(TreeNode* root) {vec.clear();traversal(root);if (vec.size() < 2) return 0;int result = INT_MAX;for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值result = min(result, vec[i] - vec[i-1]);}return result;}
};

个人问题

对于使用双指针还不够熟练。


二、二叉搜索树的众数-LeetCode 501

Leecode链接: LeetCode 501
文章链接: 代码随想录
视频链接: B站

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

示例:

输入:root = [1,null,2,2]
输出:[2]

思路

两种解法:1.中序遍历形成map数组,然后对数组进行排序,可得众数。2.递归过程中计算众数,使用一个计数器,每遇到相同的值count加1,遇到不同的值count恢复为1,然后使用maxcount记录可能成为众数出现的频率。遍历完整个树为止。

实现代码

map统计计数

//cpp
class Solution {
private:void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历if (cur == NULL) return ;map[cur->val]++; // 统计元素频率searchBST(cur->left, map);searchBST(cur->right, map);return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;
}
public:vector<int> findMode(TreeNode* root) {unordered_map<int, int> map; // key:元素,value:出现频率vector<int> result;if (root == NULL) return result;searchBST(root, map);vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); // 给频率排个序result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {// 取最高的放到result数组中if (vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};

递归过程中计数

//cpp
class Solution {
public:int count = 0;int maxcount = 0;vector<int> res;TreeNode* pre = nullptr;void test(TreeNode* root){if(root == nullptr){return;}test(root->left);if(pre == nullptr){count = 1;}else if(root->val == pre->val){count++;}else{count = 1;}if(count>maxcount){maxcount = count;res.clear();res.push_back(root->val);}else if(count == maxcount){res.push_back(root->val);}pre = root;test(root->right);return;}vector<int> findMode(TreeNode* root) {res.clear();test(root);return res;}
};

个人问题

在实现代码时,maxcount的更新位置写在了root->val != pre->val的条件分支中,导致没有存储真正的众数;count初始值最初个人设置为1,但在执行时出现访问未定义行为,原因在于count初始值手动设置为1,但pre初始值也为1,导致不能访问正确的第一个元素的值。


三.二叉树的最近公共祖先-LeeCode 236

Leecode链接: LeetCode 236
文章链接: 代码随想录
视频链接: B站

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3

思路

使用后序遍历,考虑一个一般情况,两个节点为某个父节点的左右子树,如果找到了该节点左右子树的递归函数就返回该节点的指针给父节点的这一层函数,这一层根据返回结果返回对应指针,如果都存在,表明要找的节点就在该父节点的孩子节点中,返回父节点自身即可。考虑一个特殊情况,如果两个节点互为父子节点,这时直接返回最先遇到的节点指针即可,如果一侧为空返回另一侧不为空的节点指针。

实现代码

//cpp
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL) return NULL;if(root->val==p->val||root->val==q->val)return root;TreeNode* left_p = lowestCommonAncestor(root->left,p,q);TreeNode* right_p = lowestCommonAncestor(root->right,p,q);if(left_p&&right_p)return root;else if(!left_p&&right_p) return right_p;else if(left_p&&!right_p) return left_p;else return NULL;}
};

个人问题

代码没有自己写出来。

总结

本题比较巧妙,对各个情况处理比较特殊。

这篇关于【算法训练 day23 二叉搜索树的最小绝对差、二叉搜索树的众数、二叉树的最近公共祖先】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

浅析Python中的绝对导入与相对导入

《浅析Python中的绝对导入与相对导入》这篇文章主要为大家详细介绍了Python中的绝对导入与相对导入的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1 Imports快速介绍2 import语句的语法2.1 基本使用2.2 导入声明的样式3 绝对import和相对i

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

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

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