当前位置：首页 > news >正文

代码随想录第15天：（二叉树）

news 来源：原创 2025/9/14 6:46:00

一、二叉搜索树的最小绝对差（Leetcode 530）

思路1 ：中序遍历将二叉树转化为有序数组，然后暴力求解。

class Solution:def __init__(self):# 初始化一个空的列表，用于保存树的节点值self.vec = []def traversal(self, root):# 递归函数进行中序遍历，填充self.vec列表if root is None:return  # 如果当前节点为空，直接返回# 先递归遍历左子树self.traversal(root.left)# 将当前节点的值添加到vec列表中self.vec.append(root.val)# 然后递归遍历右子树self.traversal(root.right)def getMinimumDifference(self, root):# 清空self.vec，确保每次调用时都能重新计算最小差值self.vec = []# 中序遍历树，将节点值按升序存入self.vecself.traversal(root)# 如果树中少于两个节点，则没有有效的差值可计算，返回0if len(self.vec) < 2:return 0# 初始化最小差值为正无穷大，用于后续的最小差值比较result = float('inf')# 遍历self.vec，计算相邻节点值之间的差值for i in range(1, len(self.vec)):# 计算相邻节点之间的差值，并更新最小差值result = min(result, self.vec[i] - self.vec[i - 1])# 返回最小差值return result

思路2：双指针直接操作二叉树，求任意不同节点值的最小差。

class Solution:def __init__(self):# 初始化最小差值为正无穷，表示尚未计算差值self.result = float('inf')# 初始化pre为None，用来记录上一个访问的节点self.pre = Nonedef traversal(self, cur):# 如果当前节点为空，直接返回if cur is None:return# 递归遍历左子树self.traversal(cur.left)# 计算当前节点与上一个节点的差值if self.pre is not None:  # 如果pre不为空，说明当前节点不是最左边的节点# 更新最小差值，计算当前节点与前一个节点的差值，并更新result为更小的值self.result = min(self.result, cur.val - self.pre.val)# 记录当前节点，作为下一个节点的前一个节点self.pre = cur# 递归遍历右子树self.traversal(cur.right)def getMinimumDifference(self, root):# 调用traversal进行中序遍历self.traversal(root)# 返回计算得到的最小差值return self.result

二、二叉搜索树中的众数（Leetcode 501）

思路1：利用字典

from collections import defaultdict# 定义二叉树节点类 TreeNode
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:# 在BST中搜索并统计每个节点的值的频率def searchBST(self, cur, freq_map):if cur is None:return# 统计当前节点值的频率freq_map[cur.val] += 1# 递归遍历左子树self.searchBST(cur.left, freq_map)# 递归遍历右子树self.searchBST(cur.right, freq_map)# 找出二叉搜索树中的出现频率最高的值def findMode(self, root):# 初始化一个字典来记录每个元素的频率，使用defaultdict方便处理未出现的键freq_map = defaultdict(int)result = []# 如果根节点为空，返回空列表if root is None:return result# 调用递归方法遍历二叉树并统计频率self.searchBST(root, freq_map)# 获取频率的最大值max_freq = max(freq_map.values())# 找出所有出现频率等于最大值的元素for key, freq in freq_map.items():if freq == max_freq:result.append(key)# 返回频率最高的值return result

思路二：利用二叉树性质

class Solution:def __init__(self):self.maxCount = 0  # 最大频率self.count = 0  # 当前频率self.pre = None  # 前一个节点self.result = []  # 存储众数# 用中序遍历BST，并统计节点值的频率def searchBST(self, cur):if cur is None:return# 递归遍历左子树self.searchBST(cur.left)  # 左# 中if self.pre is None:  # 第一个节点，初始化频率为1self.count = 1elif self.pre.val == cur.val:  # 当前节点与前一个节点值相同，增加频率self.count += 1else:  # 当前节点与前一个节点值不同，重新计数为1self.count = 1# 更新前一个节点为当前节点self.pre = cur  # 更新前一个节点# 如果当前节点的频率等于最大频率，将该节点值添加到结果列表if self.count == self.maxCount:  self.result.append(cur.val)# 如果当前节点的频率大于最大频率，更新最大频率，并清空结果列表，将当前节点值加入if self.count > self.maxCount:  self.maxCount = self.count  # 更新最大频率self.result = [cur.val]  # 清空结果列表并将当前节点值加入# 递归遍历右子树self.searchBST(cur.right)  # 右returndef findMode(self, root):self.count = 0  # 重置频率self.maxCount = 0  # 重置最大频率self.pre = None  # 重置前一个节点self.result = []  # 清空结果列表self.searchBST(root)  # 调用searchBST进行遍历并统计return self.result  # 返回众数

三、二叉树的最近公共祖先（Leetcode 236）

class Solution:# 定义一个函数来寻找最近公共祖先def lowestCommonAncestor(self, root, p, q):# 基本的终止条件# 1. 如果当前节点是 p 或 q，返回当前节点。# 2. 如果当前节点是 None，说明这条路径不包含 p 或 q，返回 None。if root == q or root == p or root is None:return root# 递归遍历左子树，找到 p 和 q 中其中一个的最近公共祖先left = self.lowestCommonAncestor(root.left, p, q)# 递归遍历右子树，找到 p 和 q 中其中一个的最近公共祖先right = self.lowestCommonAncestor(root.right, p, q)# 如果左子树和右子树分别都找到了 p 或 q，说明当前节点是最近公共祖先# 因为 p 和 q 分别位于左右子树if left is not None and right is not None:return root# 如果左子树找到了 p 或 q，右子树为 None，说明公共祖先在左子树if left is None and right is not None:return right# 如果右子树找到了 p 或 q，左子树为 None，说明公共祖先在右子树elif left is not None and right is None:return left# 如果左右子树都为 None，说明当前节点不是公共祖先，返回 Noneelse:return None

代码随想录第15天：（二叉树）

一、二叉搜索树的最小绝对差（Leetcode 530） 思路1 ：中序遍历将二叉树转化为有序数组，然后暴力求解。 class Solution:def __init__(self):# 初始化一个空的列表，用于保存树的节点值self.vec []def traversal(self, r…...

编程日记 2025/9/14 6:46:00

Matlab 汽车ABS的PID控制

1、内容简介 Matlab 199-汽车ABS的PID控制可以交流、咨询、答疑 2、内容说明略摘要 ： 在 ｓｉｍｕｌｉｎｋ 环境下对汽车防抱死制动系统进行数学建模 ， 采用基于…...

编程日记 2025/9/14 6:45:44

若依前后端分离版之使用Swagger

记录一下使用若依前后端分离版本中，怎么使用Swagger，以帮助初学者快速入手。 1.运行项目并查看Swagger 这里自己下载项目代码，在编译器中打开运行。这个过程跳过，我们进入系统后台界面。在系统工具、系统接口中打开Swagger页面点击test-controller和Schemas，可展开相…...

编程日记 2025/9/4 0:39:45

入侵检测snort功能概述

1. 数据包嗅探与日志记录网络流量监控：实时捕获和分析网络数据包（支持以太网、无线等）。日志记录：将数据包以二进制格式（pcap）或文本格式存储，供后续分析。 2. 协议分析与解码深度协议解析…...

编程日记 2025/9/14 5:42:58

Notepad++安装Markdown实时预览插件

具体操作打开notepad -> 插件 -> 插件管理 -> 可用 -> “Markdown Panel” -> 安装，安装完成后工具栏点击"Markdown Panel"按钮。注意：由于网络等原因可能安装失败导致工具栏没出现""Markdown Panel"按钮&am…...

编程日记 2025/8/17 19:56:42

Swift 实现 LeetCode 254：因子组合问题的递归解法全解析

文章目录摘要描述示例： 题解答案（Swift 实现）题解代码分析核心思路：举个例子： 示例测试及结果时间复杂度分析空间复杂度分析现实应用场景结合总结摘要这篇文章我们来聊聊 LeetCode 第 254 题 ——「因子的组合」。…...

编程日记 2025/9/14 6:43:35

Matlab 传感器加速度数据计算位移

1、内容简介 Matlab 195-传感器加速度数据计算位移可以交流、咨询、答疑 2、内容说明略 3、仿真分析略 4、参考论文略...

编程日记 2025/8/18 1:09:37

Ubuntu虚拟机连不上网

桥接虚拟机Ubuntu系统必须能连接到外网，不然不能更新软件安装包配置虚拟机网络（关机或者挂起状态） 第一步1.重启虚拟机网络编辑器（还原配置） 第二步2.重启虚拟机网络适配器（移除再添加） 启…...

编程日记 2025/9/14 6:45:43

大模型论文：Language Models are Unsupervised Multitask Learners(GPT2)

大模型论文：Language Models are Unsupervised Multitask Learners(GPT2) 文章地址：https://storage.prod.researchhub.com/uploads/papers/2020/06/01/language-models.pdf 摘要自然语言处理任务，例如问答、机器翻译、阅读理解和摘要&am…...

编程日记 2025/9/9 2:56:08

大模型本地部署系列（3） Ollama部署QwQ[阿里云通义千问]

大家好，我是AI研究者， 今天教大家部署一个阿里云通义千问大模型。 QwQ大模型简介 QwQ是由阿里云通义千问（Qwen）团队推出的开源推理大模型，专注于提升AI在数学、编程和复杂逻辑推理方面的能力。其核心特点包括&#x…...

编程日记 2025/9/11 21:19:10

WPF ObjectDataProvider

在 WPF（Windows Presentation Foundation）中，ObjectDataProvider 是一个非常有用的类，用于将非 UI 数据对象（如业务逻辑类或服务类）与 XAML 绑定集成。它允许在 XAML 中直接调用方法、访问属性或实例化对象，而无需编写额外的代码。以下是关于 ObjectDataProvider 的详细…...

编程日记 2025/9/14 6:43:35

《Vue Router实战教程》12.不同的历史记录模式

欢迎观看《Vue Router 实战（第4版）》视频课程不同的历史记录模式在创建路由器实例时，history 配置允许我们在不同的历史模式中进行选择。 Hash 模式 hash 模式是用 createWebHashHistory() 创建的： import { createRouter,…...

编程日记 2025/9/14 6:44:30

Dify什么？Dify 零门槛打造专属 AI 应用

Dify 是一个专注于简化大语言模型（LLM）应用开发的开源平台，旨在帮助用户通过可视化界面和模块化工具快速构建、部署和管理 AI 驱动的应用程序。以下是其核心特点： 主要功能可视化编排提供直观的界面，无需深入编码即…...

编程日记 2025/9/11 3:15:33

【Javascript】在canvas中加载shader着色器的方法（开箱即用）

功能简介可以播放，暂停shader代码，可以在js中配置shader参数（下面案例列举了所有可用参数形式）缺点这个是固定机位，没有自定义顶点着色器部分的功能，有需要可直接在class中改，或者修改后调用…...

编程日记 2025/9/14 6:41:45

华为华三模拟器解决兼容问题Win11 24H2 现在使用ENSP的问题解决了

一、Win11 24H2 现在使用ENSP的问题解决了这个Win11 的 24H2不能使用ENSP的问题已经困扰我们很久了，在之前的文章中，我们也有说明这个问题之前ENSP肯定启动会报错40 当时还建议大家先不要更新到win11的24H2版本，现在终于迎来了更新&#…...

编程日记 2025/9/9 0:27:10

五、用例篇

Bug等级：崩溃、严重、一般、次要 bug的生命周期面试高频考题：跟开发产生争执怎么办？ (1)反思自己，是不是bug描述写的不清楚 (2)站在用户思考问题，反问开发人员：“如果你是用户，你能接受这样…...

编程日记 2025/9/8 15:15:58

Mysql中的数据类型和语句概述

Mysql中的数据类型数值类整数：int，四个字节构成浮点型：float单精度浮点数，四个字节，double双精度浮点数，八个字节，decimal用于高精度计算，尤其是在金融领域。decimal&#xff…...

编程日记 2025/9/11 20:53:52

先下载依赖 npx --yes --registry https://registry.npmmirror.com npm install mqtt 在src的api创建 mes.js // 导入axios import axios from axios;// 定义一个变量,记录公共的前缀, baseURL const baseURL http://localhost:8080; const instance axios.create({ base…...

编程日记 2025/9/11 11:18:14

VLC快速制作rtsp流媒体服务器

1.安装vlc media player工具 2.打开后点击菜单媒体->流 3.添加mp4视频，选择串流 4.选择下一个 5.新目标选择 RTSP，点击添加按钮 6.端口和路径随便填写，如果推流失败就换个端口。一路操作下去 7.点击流按钮后，就可以看到下图…...

编程日记 2025/9/8 0:13:52

24FIC

一，赛前准备检材密码：2024Fic杭州Powered~by~HL! 案情简介： 2024年4月，卢某报案至警方，声称自己疑似遭受了“杀猪盘”诈骗，大量钱财被骗走。卢某透露，在与某公司交流过程中结识了员工李某。李某…...

编程日记 2025/9/10 11:10:30

P3367 【模板】并查集

题目链接：点击进入题目思路代码（路径压缩） #include <bits/stdc.h> using namespace std; const int maxn 1e6 10;int n,m,fa[maxn];int find(int x) {if(xfa[x]) return x;else return fa[x]find(fa[x]); }int unions(int x,…...

编程日记 2025/9/8 20:07:47

【leetcode hot 100 300】最长递增子序列

错误解法：在每次更新db[i]时，如果当前nums[i]>nums[i-1]就db[i-1]1，否则db[i-1] class Solution {public int lengthOfLIS(int[] nums) {int n nums.length;int[] db new int[n]; // db[i]表示到i的最长严格递增子序列的长度db[0] 1;f…...

编程日记 2025/9/9 1:31:21

jwt.io学习

jwt.io 是一个专门用于 JSON Web Token（JWT）相关操作和学习的网站，地址是：JSON Web Tokens - jwt.io具有以下主要功能： JWT 解码：能够将 JWT 令牌进行解码，展示出令牌中包含的各个部分&#xf…...

编程日记 2025/9/11 8:29:05

MySQL 优化方案大全

一、数据库设计优化 1. 表结构设计合理选择字段类型： 使用最小满足需求的类型（如TINYINT代替INT）字符串类型优先VARCHAR，固定长度用CHAR 时间类型用TIMESTAMP（4字节）或DATETIME（8字节&#xf…...

编程日记 2025/9/8 1:29:06

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模（C/C++/Java组）

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模（C/C/Java组） 时间限制: 3s 内存限制: 512MB 提交: 6633 解决: 1263 题目描述给定 n, m ，问是否存在两个不同的数 x, y 使得 1 ≤ x < y ≤ m 且 n mod x n mod y 。输入格式输入包含多…...

编程日记 2025/9/4 21:55:07

【LeetCode 题解】算法：36.有效的数独

一、问题剖析在算法领域中，数独问题是一个经典且有趣的逻辑验证题目。本题的核心任务是判断一个给定的 9x9 数独是否有效。判断的依据是数独的基本规则：数字 1-9 在每一行、每一列以及每一个 3x3 的宫内都只能出现一次。同时，题目中明确指出…...

编程日记 2025/9/8 13:32:45

C++学习之MYSQL数据库

目录 1.mysql数据库介绍 2.mysql数据库安装 3.mysql数据库启动和登录 4.mysql数据库CURD 5.mysql数据库表CURD 6.mysql数据库数据CURD 7.mysql基础综合练习 8.mysql数据库总日期和时间函数 9.mysql中函数 10.PLSQL工具使用介绍 11.ORACLE实例别名和ORACLE客户端 12.…...

编程日记 2025/9/13 4:10:37

Node.js 开发的简单 Web 服务器代码

步骤 1：创建项目文件新建名为 app.js 的文件，添加以下代码： // 1. 导入内置 http 模块 const http require(http);// 2. 创建服务器实例 const server http.createServer((req, res) > {// 设置响应头res.writeHead(200, { Content-T…...

编程日记 2025/9/12 4:06:18

Postgresql安装mysql_fdw并映射MySQL数据库

关于Postgresql映射Mysql数据库数据领导：小汪啊，他们的数据库是不是能连接上了。我：对啊，我已经读数据了。领导：那改一下吧，直接把他们的数据映射过来，体现一下我们功能的多样性。我&#…...

编程日记 2025/9/13 1:00:13

flutter 获取通话记录和通讯录

Dart SDK version is 3.7.01 dependencies:flutter:sdk: flutterpermission_handler: ^11.0.1 # 权限管理flutter_contacts: ^1.1.92call_log: ^5.0.5cupertino_icons: ^1.0.8dev_dependencies:flutter_test:sdk: flutterflutter_lints: ^5.0.0 2 contact_and_calls_page.da…...

编程日记 2025/9/13 12:11:54

一、二叉搜索树的最小绝对差（Leetcode 530）

二、二叉搜索树中的众数（Leetcode 501）

三、二叉树的最近公共祖先（Leetcode 236）

相关文章：