算法训练 | 二叉树Part7 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数

news/2024/7/25 21:27:46/文章来源:https://blog.csdn.net/qq_48896570/article/details/139276073

目录

530.二叉搜索树的最小绝对差

数组法

双指针法 ⭐

迭代法

501.二叉搜索树中的众数

双指针法

迭代法


530.二叉搜索树的最小绝对差

  • 题目链接:530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)

  • 文章讲解:代码随想录

数组法
  • 解题思路

    • 把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了

  • 代码一:数组

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;}
};
双指针法
  • 解题思路

    • 用一个pre节点记录一下cur节点的前一个节点。在二叉搜素树中序遍历的过程中直接计算。

  • 代码注意

    • 设置函数无返回值,只进行遍历

  • 代码一:双指针

class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {if (cur == NULL) return;traversal(cur->left);   // 左if (pre != NULL){       // 中result = min(result, cur->val - pre->val);}pre = cur; // 记录前一个traversal(cur->right);  // 右
}
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};
迭代法
  • 解题思路

    • 用栈模拟中序遍历的迭代法

  • 代码一:中序

class Solution {
public:int getMinimumDifference(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;int result = INT_MAX;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top();st.pop();if (pre != NULL) {              // 中result = min(result, cur->val - pre->val);}pre = cur;cur = cur->right;               // 右}}return result;}
};

501.二叉搜索树中的众数

  • 题目链接:leetcode.cn

  • 文章讲解:programmercarl.com

双指针法
  • 解题思路

    • 一个指针指向前一个节点,这样每次cur(当前节点)才能和pre(前一个节点)作比较。而且初始化的时候pre = NULL,这样当pre为NULL时候,我们就知道这是比较的第一个元素。

  • 解题步骤

    • 中序遍历:

    • 最大频率统计:

    • 存入众数结果:频率count 等于 maxCount(最大频率),当然要把这个元素加入到结果集中(以下代码为result数组)

    • 结果更新:频率count 大于 maxCount的时候,不仅要更新maxCount,而且要清空结果集(以下代码为result数组),因为结果集之前的元素都失效了。

  • 代码注意

    • if (pre != nullptr && pre->val == cur->val)

  • 代码一:双指针

class Solution {
private:int maxCount = 0; // 最大频率int count = 0; // 统计频率TreeNode* pre = NULL;vector<int> result;void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left);       // 左// 中if (pre == NULL) { // 第一个节点 //        if (pre != nullptr && pre->val == cur->val) {count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}pre = cur; // 更新上一个节点if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}searchBST(cur->right);      // 右return ;}public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};
迭代法
  • 解题思路

    • 把中序遍历转成迭代,中间节点的处理逻辑完全一样。

  • 代码一:迭代

class Solution {
public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;int maxCount = 0; // 最大频率int count = 0; // 统计频率vector<int> result;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top();st.pop();                       // 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}pre = cur;cur = cur->right;               // 右}}return result;}
};

(说明:基于代码随想录课程学习,部分内容引用代码随想录文章)

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

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

相关文章

uniapp 使用vuex 在app上能获取到state,小程序获取不到

1. 在根目录下新建store目录, 在store目录下创建index.js定义状态值import Vue from vue; import Vuex from Vuex; import Vuex from vuex; Vue.use(Vuex);const store new Vuex.Store({ state: { login: false, token: , avatarUrl: , userName: }, mutations: { lo…

轻兔推荐 —— vfox

简介 vfox 是一个跨平台且可扩展的版本管理工具&#xff0c;终于有一个可以管理所有运行环境的工具了 - 支持一键安装 Java、Node.js、Flutter、.Net、Golang、PHP、Python等多种环境 - 支持一键切换不同版本 特点 支持Windows(非WSL)、Linux、macOS! 支持不同项目不同版本、…

Spark项目实训(一)

目录 实验任务一&#xff1a;计算级数 idea步骤分步&#xff1a; 完整代码&#xff1a; linux步骤分布&#xff1a; 实验任务二&#xff1a;统计学生成绩 idea步骤分布&#xff1a; 完整代码&#xff1a; linux步骤分步&#xff1a; 实验任务一&#xff1a;计算级数 请…

力扣106. 从中序与后序遍历序列构造二叉树

Problem: 106. 从中序与后序遍历序列构造二叉树 文章目录 题目描述思路复杂度Code 题目描述 思路 具体思路参考&#xff1a; Problem: 力扣105. 从前序与中序遍历序列构造二叉树 再后序遍历中&#xff1a;每次取int rootVal postorder[postEnd];构造根节点&#xff1b;左子树…

Pytorch环境配置2.0.1+ Cuda11.7

查找cuda、cudnn、Pytorch(GPU)及cuda和NVIDIA显卡驱动对应关系 查询可支持的最高cuda版本 nvidia-smi查看支持的cuda的版本 CUDA版本对应表 我的显卡驱动是Driver Version&#xff1a;535.40.&#xff0c;那么左边对应的CUDA都可以兼容 右上角为CUDA 版本&#xff0c;可以看…

java面试框架篇(Spring常见问题、SpringBoot、SpringMVC、mybatis经典问题、SpringCloud组件)

文章目录 面试专题-java框架篇1. spring常见问题1.1. spring是什么?1.2. 谈谈你对AOP的理解1.3. 谈谈你对IOC的理解1.4. Spring Boot、 Spring MVC和Spring有什么区别1.5. spring bean 生命周期1.6. spring事务传播机制有哪些?1.7. 循环依赖1.8. spring框架中使用了哪些设计模…

作为一名前端工程师,该如何控制高并发请求呢?「如果有更好的方案,欢迎讨论」

假如现在有几十、上百个请求&#xff0c;我们该如何去控制这么高的并发呢&#xff1f; 给你一分钟时间&#xff0c;稍作思考 &#xff5e; &#x1f914; 此场景有很多&#xff0c;比如 图片或文件批量下载、RSSHub高速抓取内容。。。 第一想法是不是请求池&#xff01;&…

虚拟化技术[1]之服务器虚拟化

文章目录 虚拟化技术简介数据中心虚拟化 服务器虚拟化服务器虚拟化层次寄居虚拟化裸机虚拟化VMM无法直接捕获特权指令解决方案 服务器虚拟化底层实现CPU虚拟化内存虚拟化I/O设备虚拟化 虚拟机迁移虚拟机动态迁移迁移内容&#xff1a;内存迁移迁移内容&#xff1a;网络资源迁移迁…

NSSCTF | [SWPUCTF 2021 新生赛]no_wakeup

打开题目后&#xff0c;点击三个&#xff1f;&#xff0c;发现是一个php序列化脚本 <?phpheader("Content-type:text/html;charsetutf-8"); error_reporting(0); show_source("class.php");class HaHaHa{public $admin;public $passwd;public function…

2024第三届AIGC开发者大会圆桌论坛:AI Agent中国落地发展现状及多模态结合具身智能的发展展望

在2024年第三届AIGC开发者大会上&#xff0c;多位业内专家齐聚一堂&#xff0c;共同探讨了AI Agent在中国的落地发展现状以及多模态结合具身智能的发展前景。本次圆桌论坛的嘉宾包括&#xff1a; Fast JP作者于金龙Agent创始人莫西莫必胜作者秦瑞January Agent创始人李晨 多模…

Cesium For Unity 在Unity中无法下载的问题

Unity 下载失败&#xff0c;提供百度网盘“com.cesium.unity-1.10.0.tgz”下载链接 链接&#xff1a;https://pan.baidu.com/s/1PybXQ8EvkRofOKD6rSN66g?pwd1234 提取码&#xff1a;1234 导入方法&#xff1a; 1.打开PackageManager;Window-PackageManager 2.在PackageMan…

Vue3:封装Table 表格组件

组件官网 elementPlus : 点击跳转 封装组件 创建新的组件文件: Table.vue <!-- PropTableS &#xff1a; 父组件传递过来的数据 (对象)PropTableS.tables : 父组件传递的对象中 存放表格每行显示的数据PropTableS.keyS &#xff1a; 父组件传递过来的对象&#xff0c;里…

Golang实现递归复制文件夹

代码 package zdpgo_fileimport ("errors""os""path/filepath""strings" )// CopyDir 复制文件夹 // param srcPath 源文件夹 // param desPath 目标文件夹 // return error 错误信息 func CopyDir(srcPath, desPath string) error {…

6岁开始学习打字,10岁学懂文字编程

​你们有没有想过打字速度会影响Coding 编程能力&#xff1f; 疫情期间&#xff0c;全国中小学均不定期停止面授课程&#xff0c;改为网上教学。顷刻之间&#xff0c;电脑、智能手机等即时通讯软件成为每日学习的「良师益友」&#xff0c;常伴左右。 同时&#xff0c;学生也由…

每天五分钟深度学习框架PyTorch:创建具有特殊值的tensor张量

本文重点 tensor张量是一个多维数组,本节课程我们将学习一些pytorch中已经封装好的方法,使用这些方法我们可以快速创建出具有特殊意义的tensor张量。 创建一个值为空的张量 import torch import numpy as np a=torch.empty(1) print(a) print(a.dim()) print(s.shape) 如图…

本地部署 MiniCPM-Llama3-V 2.5

本地部署 MiniCPM-Llama3-V 2.5 0. 引言1. 性能评估2. 典型示例3. 本地部署4. 运行 WebUI Demo5. vLLM 部署 0. 引言 MiniCPM-Llama3-V 2.5 是 MiniCPM-V 系列的最新版本模型&#xff0c;基于 SigLip-400M 和 Llama3-8B-Instruct 构建&#xff0c;共 8B 参数量&#xff0c;相较…

Linux java jni调用C++封装动态库

由于项目中java需要调用第三方提供的C动态库&#xff1b;由于第三方动态库传入的参数较多&#xff0c;还伴随着指针传入操作&#xff0c;导致java调用极为不便&#xff01;因此催生出对于第三方的C动态库进行二次封装。java调用只需按结构传入一个结构化的string即可。话不多说…

CSS文本粒子动画特效之爱心粒子文字特效-Canvas

1. 效果图 2.完整代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><style>body,html {margin: 0;paddin…

嵌入式学习——3——UDP TFTP简易文件传输

tftp协议概述 简单文件传输协议&#xff0c;适用于在网络上进行文件传输的一套标准协议&#xff0c;使用UDP传输 特点&#xff1a; 是应用层协议 基于UDP协议实现 数据传输模式 octet&#xff1a;二进制模式&#xff08;常用&#xff09; mail&#xff1a;已经不再支持 TFTP通信…

【Spring】深入学习AOP编程思想的实现原理和优势

【切面编程】深入学习AOP编程思想的实现原理和优势 前言AOP的由来及AOP与代理的关系AOP的实现方式详解静态代理动态代理 AOP的应用场景记录日志权限控制数据库事务控制缓存处理异常处理监控管理 AOP的底层实现全流程解析Spring AOP的简介动态代理的实现原理Spring AOP的实现原理…