Leetcode算法训练日记 | day21

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

1.题目

Leetcode：第 530 题

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

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

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

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

2.解题思路

1.一般递归法：使用递归法遍历整个二叉树，得出保存所有节点元素的数组，再遍历数组找出最小差值。

2.双指针递归法：通过栈来进行二叉树的遍历，模拟了二叉树的中序遍历。在遍历过程中，始终保持一个指向前一个访问节点的指针 pre，并在每次访问新节点时更新最小差值 result。由于栈的特性，可以保证在每次从栈中弹出节点时，都已经访问过它的所有左子树节点，因此我们可以计算当前节点与前一个节点的差值。这样，可以在一次遍历中找到所有节点值之间的最小差值。

3.迭代法：使用迭代法遍历整个二叉树，找出不同节点值之间的最小差值 。

3.实现代码

// 一、实现计算二叉树最小差值的算法（一般递归法）。
class Solution1 {
public:vector<int> vec; // 定义一个vec，用于存储二叉树节点的值，// 定义一个名为traversal的私有成员函数，用于执行二叉树的中序遍历。// 参数root是当前遍历到的二叉树节点指针。void traversal(TreeNode* root) {if (root == NULL) return; // 如果当前节点为空，直接返回，不执行任何操作。traversal(root->left); // 递归调用traversal函数遍历当前节点的左子树。vec.push_back(root->val); // 访问当前节点，将其值添加到vec中。traversal(root->right); // 递归调用traversal函数遍历当前节点的右子树。}// 定义一个名为getMinimumDifference的公共成员函数，用于计算给定二叉树中所有节点值之间的最小差值。// 参数root是二叉树的根节点指针。int getMinimumDifference(TreeNode* root) {vec.clear(); // 清空vec，为新的中序遍历做准备。traversal(root); // 调用traversal函数，传入根节点，执行中序遍历，并将结果存储在vec中。if (vec.size() < 2) return 0;  // 检查vec中的元素数量，如果小于2，则不存在有效的差值，返回0。int result = INT_MAX;// 初始化最小差值result为INT_MAX，表示最大的整数值。for (int i = 1; i < vec.size(); i++) {// 遍历vec中的元素，计算并更新最小差值。result = min(result, vec[i] - vec[i - 1]);   // 计算当前元素与前一个元素的差值，并与已知的最小差值result进行比较。}return result; // 返回计算得到的最小差值。}
};//  二、实现计算二叉树最小差值的算法（双指针递归法）。
class Solution2 {
public:int result = INT_MAX; // 初始化结果变量result为整数的最大值INT_MAX，表示开始时最小差值为无穷大。TreeNode* pre = NULL; // 定义一个指向TreeNode的指针pre，用于记录遍历过程中前一个访问的节点。// 定义一个名为traversal的私有成员函数，用于执行二叉树的遍历。// 参数cur是当前遍历到的二叉树节点指针。void traversal(TreeNode* cur) {if (cur == NULL) return; // 如果当前节点为空，直接返回，不执行任何操作。traversal(cur->left); // 递归调用traversal函数遍历当前节点的左子树。if (pre != NULL) {  // 如果pre不为空，说明我们已经遍历过至少一个节点，可以计算差值。result = min(result, cur->val - pre->val);// 更新结果变量result为当前节点值与前一个节点值之差的最小值。}pre = cur; // 更新pre为当前节点，因为在下一次递归调用中，当前节点将成为新的前一个节点。traversal(cur->right);  // 递归调用traversal函数遍历当前节点的右子树。}// 定义一个名为getMinimumDifference的公共成员函数，用于启动遍历过程并返回最小差值。// 参数root是二叉树的根节点指针。int getMinimumDifference(TreeNode* root) {traversal(root);// 调用traversal函数，传入根节点，开始遍历二叉树。return result; // 返回结果result，即二叉树中所有节点值之间的最小差值。}
};//  三、实现计算二叉树最小差值的算法（迭代法）。
class Solution3 {
public:// 定义一个名为getMinimumDifference的公共成员函数，用于计算给定二叉树中所有节点值之间的最小差值。// 参数root是二叉树的根节点指针。int getMinimumDifference(TreeNode* root) {stack<TreeNode*> st; // 定义一个栈st，用于存放二叉树的节点指针，辅助进行迭代遍历。TreeNode* cur = root; // 定义一个当前节点指针cur，初始指向根节点。TreeNode* pre = NULL; // 定义一个前一个节点指针pre，初始为NULL，用于记录遍历过程中的前一个节点值。int result = INT_MAX; // 初始化结果result为整数的最大值INT_MAX，表示开始时最小差值为无穷大。while (cur != NULL || !st.empty()) { // 当当前节点不为空，或者栈st不为空时，继续遍历。if (cur != NULL) { // 如果当前节点不为空，执行以下操作：st.push(cur); // 将当前节点压入栈st。cur = cur->left; // 将cur更新为当前节点的左子节点，准备遍历左子树。}else { // 如果当前节点为空，执行以下操作：cur = st.top(); // 将栈顶节点作为当前节点。st.pop(); // 弹出栈顶节点。// 如果pre不为空，说明我们之前已经访问过至少一个节点，可以计算差值。if (pre != NULL) {result = min(result, cur->val - pre->val); // 更新结果result为当前节点值与前一个节点值之差的最小值。}pre = cur; // 更新pre为当前节点，因为在下一次迭代中，当前节点将成为新的前一个节点。cur = cur->right; // 将cur更新为当前节点的右子节点，准备遍历右子树。}}return result; // 返回结果result，即二叉树中所有节点值之间的最小差值。}
};

二、二叉搜索树中的众数

1.题目

Leetcode：第 501 题

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

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

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1：

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

示例 2：

输入：root = [0]
输出：[0]
2.解题思路

通过中序遍历二叉搜索树，并在遍历过程中跟踪连续出现相同元素的次数。如果遇到不同的元素，或者遍历结束，则将当前的连续元素数量与最大连续元素数量进行比较。如果相等，就将该元素的值添加到结果向量中。最终，findMode 函数返回包含出现次数最多元素的数组。

3.实现代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数，用于创建一个TreeNode实例。// 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、查找二叉搜索树中的众数（递归法）。
class Solution1 {
public:int maxCount = 0; // 定义一个整数maxCount，用于存储遍历过程中遇到的最长连续元素的数量。int count = 0;// 定义一个整数count，用于存储当前连续出现的元素数量。TreeNode* pre = NULL; // 定义一个指向TreeNode的指针pre，用于记录遍历过程中前一个访问的节点。vector<int> result; // 定义一个容器result，用于存储出现次数最多的元素。// 定义一个名为searchBST的私有成员函数，用于递归遍历二叉搜索树。// 参数cur是当前遍历到的二叉树节点指针。void searchBST(TreeNode* cur) {if (cur == NULL) return; // 如果当前节点为空，直接返回。searchBST(cur->left); // 递归遍历当前节点的左子树。// 如果pre为空（即这是遍历的起始节点），或者当前节点的值与pre相同（即连续出现），则增加count。if (pre == NULL) {count = 1;}else if (pre->val == cur->val) {count++;}else {count = 1; // 否则，重置count为1。}pre = cur; // 更新pre为当前节点。// 如果当前的连续元素数量count等于最大连续元素数量maxCount，则将当前节点的值添加到结果result中。if (count == maxCount) {result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 清空result，之前result里的元素都失效了result.push_back(cur->val);}searchBST(cur->right); // 递归遍历当前节点的右子树。return; // 这里返回是为了结束函数调用，实际上在递归中不需要显式返回。}// 定义一个名为findMode的公共成员函数，用于启动搜索过程并返回出现次数最多的元素列表。// 参数root是二叉树的根节点指针。vector<int> findMode(TreeNode* root) {count = 0; // 重置当前连续元素数量。maxCount = 0; // 重置最大连续元素数量。pre = NULL; // 重置前一个访问的节点指针。result.clear(); // 清空结果，为新的搜索做准备。searchBST(root); // 调用searchBST函数，传入根节点，开始递归遍历。return result;// 返回结果result，包含出现次数最多的元素。}
};// 二、查找二叉搜索树中的众数（迭代法）。
class Solution2 {
public:// 定义一个名为findMode的公共成员函数，用于启动搜索过程并返回出现次数最多的元素列表。// 参数root是二叉树的根节点指针。vector<int> findMode(TreeNode* root) {stack<TreeNode*> st; // 定义一个栈st，用于存放二叉树的节点指针，辅助进行迭代遍历。TreeNode* cur = root; // 定义一个当前节点指针cur，初始指向根节点。TreeNode* pre = NULL; // 定义一个前一个节点指针pre，初始为NULL，用于记录遍历过程中的前一个节点值。int maxCount = 0; // 初始化最大连续元素数量maxCount为0。int count = 0; // 初始化当前连续元素数量count为0。vector<int> result; // 定义一个容器result，用于存储出现次数最多的元素。// 当当前节点不为空，或者栈st不为空时，继续遍历。while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur); // 如果当前节点不为空，将当前节点压入栈st。cur = cur->left; // 将cur更新为当前节点的左子节点，准备遍历左子树。}else {cur = st.top(); // 如果当前节点为空，将栈顶节点作为当前节点。st.pop(); // 弹出栈顶节点。// 如果pre为空（即这是遍历的起始节点），则重置count为1。if (pre == NULL) {count = 1;}// 如果当前节点的值与pre相同（即连续出现），则增加count。else if (pre->val == cur->val) {count++;}else {count = 1; // 否则，重置count为1。}pre = cur; // 更新pre为当前节点。// 如果当前的连续元素数量count等于最大连续元素数量maxCount，则将当前节点的值添加到结果result中。if (count == maxCount) {result.push_back(cur->val);}// 如果当前的连续元素数量count大于最大连续元素数量maxCount，则更新maxCount并清空result，将当前节点的值添加到result中。if (count > maxCount) {maxCount = count;result.clear();result.push_back(cur->val);}cur = cur->right; // 将cur更新为当前节点的右子节点，准备遍历右子树。}}return result; // 返回结果result，包含出现次数最多的元素。}
};

三、二叉树的最近公共祖先

1.题目

Leetcode：第 236 题

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

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

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1
2.解题思路

使用递归法遍历二叉树，找到p和q节点，并求出最近公共祖先。

3.实现代码
#include <iostream>
#include <vector>
using namespace std;// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数，用于创建一个TreeNode实例。// 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 寻找二叉树的最近公共祖先（递归法）
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点root是节点q或p之一，或者root为空，则返回当前节点root作为可能的最近公共祖先。if (root == q || root == p || root == NULL) return root;// 递归调用lowestCommonAncestor函数在当前节点root的左子树中查找p和q的最近公共祖先，并将结果存储在left。TreeNode* left = lowestCommonAncestor(root->left, p, q);// 递归调用lowestCommonAncestor函数在当前节点root的右子树中查找p和q的最近公共祖先，并将结果存储在right。TreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果在左右子树中都找到了p和q的最近公共祖先（即left和right都不为空），则当前节点root是p和q的最近公共祖先。if (left != NULL && right != NULL) return root;// 如果只在右子树中找到了p和q的最近公共祖先（即left为空，right不为空），则返回right。if (left == NULL && right != NULL) return right;// 如果只在左子树中找到了p和q的最近公共祖先（即left不为空，right为空），则返回left。else if (left != NULL && right == NULL) return left;// 如果在左右子树中都没有找到p和q的最近公共祖先（即left和right都为空），或者p和q都位于当前节点的同一侧（左或右），则返回NULL。else {return NULL;}}
};

ps：以上皆是本人在探索算法旅途中的浅薄见解，诚挚地希望得到各位的宝贵意见与悉心指导，若有不足或谬误之处，还请多多指教。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/303549.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

『大模型笔记』LLMs入门：从头理解与编码LLM的自注意力机制

『大模型笔记』LLMs入门：从头理解与编码LLM的自注意力机制

LLMs入门&#xff1a;从头理解与编码LLM的自注意力机制 这里直接引用我语雀上的的文章&#xff1a;《从头理解与编码LLM的自注意力机制》
阅读更多...
python第四次作业

python第四次作业

1、找出10000以内能被5或6整除&#xff0c;但不能被两者同时整除的数&#xff08;函数&#xff09; def func():for i in range(10001):if (i % 5 0 or i % 6 0) and i % 30 ! 0:print(i,end " ")func() 2、写一个方法&#xff0c;计算列表所有偶数下标元素的…
阅读更多...
AWVS/Acunetix Premium V24.3.2403高级版漏洞扫描器

AWVS/Acunetix Premium V24.3.2403高级版漏洞扫描器

前言 Acunetix Premium 是一种 Web 应用程序安全解决方案&#xff0c;用于管理多个网站、Web 应用程序和 API 的安全。集成功能允许您自动化 DevOps 和问题管理基础架构。 Acunetix Premium&#xff1a;全面的 Web 应用程序安全解决方案 Web 应用程序对于企业和组织与客户、…
阅读更多...
优先级队列

优先级队列

优先级队列的基本使用 模拟实现上面的接口函数&#xff0c;优先级队列不是队列&#xff0c;而是类似一个堆一样的东西&#xff0c;我们先来试试它的接口函数是怎么个样子的。 需要包含的头文件是queue。 #include<iostream> #include<queue> using namespace std;…
阅读更多...
Qt Creator 新建项目

Qt Creator 新建项目

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、使用 Qt Creator 新建项目 1、新建项目 2、选择项目模板 3、选择项目路径 4、选择构建系统 5…
阅读更多...
基于达梦数据库开发-python篇

基于达梦数据库开发-python篇

文章目录 前言一、搭建demo前提初始化简单demo 二、可能出现的异常情况DistutilsSetupErrorNo module named dmPythonlist报错 总结 前言 出于信创的考虑&#xff0c;近年来基于国产数据库达梦的应用开发逐渐变多。本文将介绍在windows环境下基于DM8版本的python的简单开发使用…
阅读更多...
PaddleVideo：onnx模型导出

PaddleVideo：onnx模型导出

本文节介绍 PP-TSM 模型如何转化为 ONNX 模型&#xff0c;并基于 ONNX 引擎预测。 1&#xff1a;环境准备 安装 Paddle2ONNX python -m pip install paddle2onnx 安装 ONNXRuntime # 建议安装 1.9.0 版本&#xff0c;可根据环境更换版本号 python -m pip install onnxrunti…
阅读更多...
windows10/11重启电脑自动开启热点

windows10/11重启电脑自动开启热点

windows10/11重启电脑自动开启热点 一、前言二、要做的所有步骤及原理2.1 下载文件2.2 打开系统运行PS1文件限制2.3 给.bat文件创建桌面快捷方式2.4 关闭热点&#xff0c;双击快捷方式&#xff0c;查看热点是否成功开启2.5 将快捷方式加入开启自启 一、前言 有某种场景&#x…
阅读更多...
华为数通配置旁挂二层组网直接转发实验

华为数通配置旁挂二层组网直接转发实验

配置旁挂二层组网直接转发示例 组网图形 组网需求 AC组网方式&#xff1a;旁挂二层组网。DHCP部署方式&#xff1a; AC作为DHCP服务器为AP分配IP地址。汇聚交换机SwitchB作为DHCP服务器为STA分配IP地址。业务数据转发方式&#xff1a;直接转发。 数据规划 表1 AC数据规划表 …
阅读更多...
【C++第二阶段】文件操作

【C++第二阶段】文件操作

以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 文件操作文件写入流程简单的demo写操作 文件读流程二进制写文件二进制读文件 文件操作 文件写入流程 写文件包括以下几个步骤 1.包含头文件 2.创建流对象 3.打开文件&#xff0…
阅读更多...
41-软件部署实战（中）：IAM系统生产环境部署实战

41-软件部署实战（中）：IAM系统生产环境部署实战

下面四个步骤来部署IAM应用&#xff1a; 在服务器上部署IAM应用中的服务。配置Nginx&#xff0c;实现反向代理功能。通过反向代理&#xff0c;我们可以通过Nginx来访问部署在内网的IAM服务。配置Nginx&#xff0c;实现负载均衡功能。通过负载均衡&#xff0c;我们可以实现服务…
阅读更多...
合并两个单链表

合并两个单链表

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 但行前路&#xff0c;不负韶华&#…
阅读更多...
【教学类-50-05】20240410“数一数”4类图片添加“难度星号”

【教学类-50-05】20240410“数一数”4类图片添加“难度星号”

作品展示 背景需求 前期已经制作了四类“数一数”学具&#xff0c;具体样式如下&#xff1a; 1、难度1.0 【教学类-50-01】20240407“数一数”图片样式01&#xff1a;图形与边框不重合&#xff0c;图形和其他图形不相交-CSDN博客文章浏览阅读293次&#xff0c;点赞20次&…
阅读更多...
STL容器之unordered_set类

STL容器之unordered_set类

文章目录 STL容器之unordered_set类1、unordered系列关联式容器2、unordered_set2.1、unordered_set介绍2.2、unordered_set的使用2.2.1、unordered_set的常见构造2.2.2、unordered_set的迭代器2.2.3、unordered_set的容量2.2.4、unordered_set的增删查2.2.5、unordered_set的桶…
阅读更多...
考研数学｜武忠祥各阶段用书搭配及分享

考研数学｜武忠祥各阶段用书搭配及分享

看到有人问武忠祥老师&#xff0c;不请自来 武忠祥老师&#xff0c;绝对的宝藏老师&#xff0c;我在考研强化阶段的时候听过他的强化课程&#xff0c;听完之后&#xff0c;很多问题都想通了&#xff0c;所以&#xff0c;如果有人想问武忠祥老师行不行&#xff0c;那我就一个字…
阅读更多...
短剧在线搜索PHP网站源码

短剧在线搜索PHP网站源码

源码简介 短剧在线搜索PHP网站源码&#xff0c;自带本地数据库500数据&#xff0c;共有6000短剧视频&#xff0c;与短剧猫一样。 搭建环境 PHP 7.3 Mysql 5.6 安装教程 1.上传源码到网站目录中 2.修改【admin.php】中&#xff0c; $username ‘后台登录账号’; $passwor…
阅读更多...
(2022级）成都工业学院数据库原理及应用实验一：CASE工具概念数据模型建模

(2022级）成都工业学院数据库原理及应用实验一：CASE工具概念数据模型建模

写在前面 1、基于2022级软件工程/计算机科学与技术实验指导书 2、代码仅提供参考 3、如果代码不满足你的要求&#xff0c;请寻求其他的途径 运行环境 window11家庭版 PowerDesigner 16.1 实验要求 某医院一个门诊部排班管理子系统涉及如下信息&#xff1a; 若干科室&a…
阅读更多...
【.Net】Polly

【.Net】Polly

文章目录 概述服务熔断、服务降级、服务限流、流量削峰、错峰、服务雪崩Polly的基本使用超时策略悲观策略乐观策略 重试策略请求异常响应异常 降级策略熔断策略与策略包裹&#xff08;多种策略组合&#xff09; 参考 概述 Polly是一个被.NET基金会支持认可的框架&#xff0c;同…
阅读更多...
通过 Cookie、Redis共享Session 和 Spring 拦截器技术，实现对用户登录状态的持有和清理（四）

通过 Cookie、Redis共享Session 和 Spring 拦截器技术，实现对用户登录状态的持有和清理（四）

本篇内容对应 “2.5 开发登录、退出功能” 小节 “4.7 优化登陆模块” 小节 2.6 显示登录信息 2.7 账号设置 2.8 检查登录状态 登录功能的流程是什么&#xff1f; UUID为什么不会重复&#xff1f; 因为UUID是基于mac物理地址、时间戳、随机数等信息生成。因此UUID居于极高的唯…
阅读更多...
【鸿蒙开发】ArkTS和组件

【鸿蒙开发】ArkTS和组件

1. 初识ArkTS语言 ArkTS是HarmonyOS优选的主力应用开发语言。ArkTS围绕应用开发在TypeScript生态基础上做了进一步扩展&#xff0c;继承了TS的所有特性。 当前&#xff0c;ArkTS在TS的基础上主要扩展了如下能力&#xff1a; 基本语法&#xff1a;ArkTS定义了声明式UI描述、自…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023