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

代码随想录 day 18 二叉树

第六章 二叉树part06

详细布置
530.二叉搜索树的最小绝对差

需要领悟一下二叉树遍历上双指针操作,优先掌握递归
题目链接/文章讲解:https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解:https://www.bilibili.com/video/BV1DD4y11779

501.二叉搜索树中的众数

和 530差不多双指针思路,不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看,然后看我的视频讲解。
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解:https://www.bilibili.com/video/BV1fD4y117gp

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

本题其实是比较难的,可以先看我的视频讲解
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解:https://www.bilibili.com/video/BV1jd4y1B7E2

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

题目链接

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/

解题思路

还是二叉搜索的中序遍历单调递增的特性,判断相邻俩个节点的差值的绝对值和最小值比较,最终求出最小值
递归误区:想着直接在getMinimumDifference函数进行递归,但是遇到空节点 返回int的值是什么? 发现终止条件确定不下来,所以要重新考虑递归函数的参数和返回值。
这时考虑到新建递归函数,遇到null节点return ,递归函数返回值是void,参数就是节点,因为每次操作的全局变量就是结果,不需要返回值。

code

    private TreeNode pre=null;int min=Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root ==null ) return 0;recursion(root);return min;}public void recursion(TreeNode root){if(root==null){return;}recursion(root.left);if(pre!=null&&Math.abs(root.val-pre.val)<min){min=Math.abs(root.val-pre.val);}pre=root;recursion(root.right);}

501.二叉搜索树中的众数

题目链接

https://leetcode.cn/problems/find-mode-in-binary-search-tree/

解题思路

中序遍历相邻,要考虑如何更新,当前和前一个相同,count++;

code

    ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {if(root==null){return null;}resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;recursion(root);int[] res = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {res[i] = resList.get(i);}return res;}public void recursion(TreeNode root){if(root==null){return;}recursion(root.left);int rootValue=root.val;// 计数if (pre == null || rootValue != pre.val) {count = 1;} else {count++;}// 更新结果以及maxCountif (count > maxCount) {resList.clear();resList.add(rootValue);maxCount = count;} else if (count == maxCount) {resList.add(rootValue);}pre = root;recursion(root.right);}

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

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

解题思路

后序遍历的回溯过程
如果p节点下有q这种情况,代码已经包含了这种逻辑,就是递归终止条件如果遇到p就是直接返回p,根本不用向下递归是否有q了,题目说了一定有p和q节点,所以最后的回溯到第一层后最近公共祖先就是p。

code

    //后序遍历回溯的思想,把找到的p和q向上返回,左右中,中的时候判断是否符合public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//1.递归函数的终止条件//等于null返回nullif(root==null){return null;}//等与p或q返回给上层的递归函数if(root==p||root==q){return root;}//单层递归逻辑,left或right要么是null要么是p或qTreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);//处理中的逻辑//left和right都不等于null,那么一定包含了p和q ,这个root的节点就是最近的公共祖先if(left!=null&&right!=null){return root;}//left 找到了p或q节点,回溯给上一层if(left!=null){return left;}//right 找到了p或q节点,回溯给上一层if(right!=null){return right;}//这里是left和right都等于null,那么返回nullreturn null;}

image.png

相关文章:

代码随想录 day 18 二叉树

第六章 二叉树part06 详细布置 530.二叉搜索树的最小绝对差 需要领悟一下二叉树遍历上双指针操作&#xff0c;优先掌握递归 题目链接/文章讲解&#xff1a;https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%B…...

降雨量预测 | Matlab基于ARIMA-RBF降雨量预测

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 降雨量预测 | Matlab基于ARIMA-RBF降雨量预测 注&#xff1a;程序和数据放在一个文件夹。 程序语言为matlab&#xff0c;程序可出预测效果图&#xff0c;指标图; 代码特点&#xff1a;参数化编程、参数可方便更改、代…...

包含示例和模板的流程文档指南

当您的业务扩展时&#xff0c;您会得到越来越多的移动部件&#xff0c;并且需要有人来跟踪复杂性。人员和任务需要以尽可能最高效的方式进行组织&#xff0c;并且您必须找到某种方法让员工知道如何执行有效完成工作所需的流程。 为了使流程可重复&#xff0c;需要对其进行记录…...

51单片机嵌入式开发:15、STC89C52RC操作蜂鸣器实现一个music音乐播放器的音乐盒

STC89C52RC操作蜂鸣器实现一个music音乐播放器的音乐盒 1 概述2 蜂鸣器操作方法3 蜂鸣器发出音声4 硬件电路5 软件实现6 整体工程&#xff1a;7 总结 1 概述 要实现一个基于STC89C52RC单片机的音乐盒&#xff0c;可以按照以下步骤进行&#xff1a; &#xff08;1&#xff09;硬…...

B树(B-Tree)数据结构

1. 什么是B树&#xff1f; B树&#xff08;B-Tree&#xff09;是一种多路搜索树&#xff0c;用于存储和检索大量数据。它是自适应的&#xff0c;适用于各种存储设备和各种数据量。B树的特点是高效的搜索、插入和删除操作&#xff0c;且可以在各种情况下保持树的平衡。 2. B树…...

【BUG】已解决:ModuleNotFoundError: No module named ‘torch‘

已解决&#xff1a;ModuleNotFoundError: No module named ‘torch‘ 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就职于医疗科技公司&#xff0c;热衷分享知识&#xff0c;武汉城市…...

数据结构——队列(链式结构)

一、队列链式结构定义 队列的链式存储结构是一种用链表实现的队列,它不像顺序存储结构那样需要预先分配固定大小的空间。链式存储结构的队列由节点组成,每个节点包括数据和指向下一个节点的指针。队列的链式存储结构可以动态地分配内存,更灵活地处理数据。在链式存储结构中…...

解决GoLand添加GOROOT提示The selected directory is not a valid home for Go Sdk的问题

现象 解决 在Go安装路径下找到zversion.go文件&#xff0c;我的在D:\Program Files\Go1.21.1\src\runtime\internal\sys下面 打开文件&#xff0c;添加如下内容&#xff1a; const TheVersion go1.21.1保存后再重新添加GOROOT即可...

51单片机(STC8H8K64U/STC8051U34K64)_RA8889驱动TFT大屏_I2C_HW参考代码(v1.3) 硬件I2C方式

本篇介绍单片机使用硬件I2C方式控制RA8889驱动彩屏。 提供STC8H8K64U和STC8051U34K64的参考代码。 【硬件部份】STC8H8K64U/STC8051U34K64 RA8889开发板 7寸TFT 800x480 1. 实物连接图&#xff1a;STC8H8K64URA8889开发板&#xff0c;使用P2口I2C接口&#xff1a; 2.实物连…...

【Python其他检查字符串占字节数的方法】

在Python中&#xff0c;检查字符串在特定编码下占用的字节数&#xff0c;最标准且常用的方法是通过字符串的.encode()方法将字符串转换为字节串&#xff0c;然后使用len()函数来获取这个字节串的长度。这是因为字符串&#xff08;在Python 3中&#xff09;是以Unicode形式存储的…...

梧桐数据库: 数据库技术中的重写子查询技术

数据库技术中的重写子查询技术&#xff0c;是数据库查询优化的一种重要手段。该技术主要通过改变子查询的形式&#xff0c;使其在执行效率和性能上得到优化。以下是对重写子查询技术的详细解析&#xff1a; 一、定义与目的 定义&#xff1a;重写子查询技术是指在数据库查询优…...

PHP连接MySQL数据库

PHP本身不具备操作MySQL数据库的能力&#xff0c;需要借助MySQL扩展来实现。 1、PHP加载MySQL扩展&#xff1a;php.ini文件中。&#xff08;不要用记事本打开&#xff09; 2、PHP中所有扩展都是在ext的文件夹中&#xff0c;需要指定扩展所在路径&#xff1a;extension_dir。 3、…...

STM32自己从零开始实操:PCB全过程

一、PCB总体分布 以下只能让大家看到各个模块大致分布在板子的哪一块&#xff0c;只能说每个人画都有自己的理由&#xff1a; 电源&#xff1a;从外部接入电源&#xff0c;5V接到中间&#xff0c;向上变成4V供给无线&#xff0c;向下变成3V供给下面的接口&#xff08;也刻意放…...

error `slot` attributes are deprecated vue/no-deprecated-slot-attribute

旧的代码如下&#xff1a; <template slot"title">{{ item.title }}</template> {{ item.title }} 是一个模板标签&#xff0c;它在模板中插入了一个元素&#xff08;slot&#xff09;&#xff0c;并指定了元素的名称为 “title”。这个标签在模板中显示…...

Websocket自动消息回复服务端工具

点击下载《Websocket自动消息回复服务端工具》 1. 前言 在进行Websocket开发时&#xff0c;前端小伙伴通常是和后端开发人员同步进行项目开发&#xff0c;经常会遇到后端开发人员接口还没开发完&#xff0c;也没有可以调试的环境&#xff0c;只能按照接口文档进行“脑回路开发…...

【软考】UML中的关联关系

目录 一、说明二、具体类型2.1 普通关联2.2 单向关联2.3 双向关联2.4 自关联2.4 聚合关系&#xff08;Aggregation&#xff09;2.5 组合关系&#xff08;Composition&#xff09; 三、关联关系中的多重性 一、说明 1.UML&#xff08;Unified Modeling Language&#xff0c;统一…...

贪吃蛇超精讲(C语言)

前言 如果你还是个萌新小白&#xff0c;那么该项目的攻克过程一定会十分艰难。虽然作者已经将文章尽可能写的逻辑清晰&#xff0c;内容详细。但所谓“纸上得来终觉浅”&#xff0c;在讲到陌生结构和函数时&#xff0c;大家请一定自己动手去敲一遍代码&#xff0c;这很重要&…...

掌握Rust:函数、闭包与迭代器的综合运用

掌握Rust&#xff1a;函数、闭包与迭代器的综合运用 引言&#xff1a;解锁 Rust 高效编程的钥匙函数定义与模式匹配&#xff1a;构建逻辑的基石高阶函数与闭包&#xff1a;代码复用的艺术迭代器与 for 循环&#xff1a;高效数据处理的引擎综合应用案例&#xff1a;构建一个简易…...

【LeetCode】80.删除有序数组中的重复项II

1. 题目 2. 分析 3. 代码 class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums) < 3:return len(nums)i 0j 1k 2while(k < len(nums)):if (nums[i] nums[j]):while(k < len(nums) and nums[j] nums[k] ):k1if (k < len(nums…...

Armpro搭建教程全开源版的教程

Armpro搭建教程 全开源版的教程&#xff0c;其他未知 资源宝整理分享 www.httple.net 首先ssh执行指令安装运行环境 yum install java-1.8.0-openjdk* -y导入文件服务器 导入arm.zip到www目录下然后解压 导入jar包.zip到www目录然后解压 导入basic.zip到www目录然后解压在宝塔…...

nginx基本原理

进程模型 当nginx启动之后&#xff0c;会有一个master进程和多个worker进程。默认是一个worker进程。 master进程的作用&#xff1a;接收来自外界信号&#xff0c;向各worker进程发送信号&#xff0c;监控worker进程的运行状态&#xff0c;当worker进程在异常情况下退出后&am…...

在 CI/CD Pipeline 中实施持续测试的最佳实践!

随着软件开发周期的不断加快&#xff0c;持续集成&#xff08;CI&#xff09;和持续交付/部署&#xff08;CD&#xff09;已经成为现代软件开发的重要组成部分。在这一过程中&#xff0c;持续测试的实施对于确保代码质量、提高发布效率至关重要。本文将详细介绍在CI/CD流水线中…...

数据结构 —— B树

数据结构 —— B树 B树B树的插入操作分裂孩子分裂父亲分裂 我们之前学过了各种各样的树&#xff0c;二叉树&#xff0c;搜索二叉树&#xff0c;平衡二叉树&#xff0c;红黑树等等等等&#xff0c;其中平衡二叉树和红黑树都是控制树的高度来控制查找次数。 但是&#xff0c;这都…...

Redis 深度历险:核心原理与应用实践 - 读书笔记

目录 第一章 基础应用篇Zset并发问题 - 分布式锁再谈分布式锁客户端在请求时加锁失败策略redis异步队列位图Hyperloglog布隆过滤器GeoHashscan 命令字典结构rehash扩容大 key 扫描 第二章 原理篇线程IO模型RESP 序列化协议持久化管道事务PubSub内存管理 第三章 集群篇CAP主从同…...

微服务重启优化kafka+EurekaNotificationServerListUpdater

由于遇到服务重启导致的业务中断等异常&#xff0c;所以计划通过kafkaeureka实现服务下线通知&#xff0c;来尽可能规避这类问题。 如果可以升级spring&#xff0c;则可以考虑nacos等更为方便的方案&#xff1b; 程序优化&#xff1a; 1.默认启用的为 PollingServerListUpdater…...

removeIf 方法设计理念及泛型界限限定

ArrayList 中的 removeIf 方法是 Java 8 中引入的集合操作方法之一。它使用了 Predicate 接口作为参数&#xff0c;以便根据指定的条件移除集合中的元素。以下是对 removeIf 方法入参设计的详细解释&#xff1a; Predicate 接口 Predicate 是一个函数式接口&#xff0c;定义了…...

kubernetes集群部署elasticsearch集群,包含无认证和有认证模式

1、背景&#xff1a; 因公司业务需要&#xff0c;需要在测试、生产kubernetes集群中部署elasticsearch集群&#xff0c;因不同环境要求&#xff0c;需要部署不同模式的elasticsearch集群&#xff0c; 1、测试环境因安全性要求不高&#xff0c;是部署一套默认配置&#xff1b; 2…...

Java 随笔记: 集合与泛型

文章目录 1. 集合框架概述2. 集合接口2.1 Collection 接口2.2 List 接口2.3 Set 接口2.4 Map 接口 3. 集合的常用操作3.1 添加元素3.2 删除元素3.3 遍历元素3.4 判断大小3.5 判断是否为空 4. 迭代器4.1 迭代器的作用4.2 迭代器的使用4.3 迭代器与增强 for 循环4.4 迭代器的注意…...

SurrealDB:高效构建实时Web应用的数据库

SurrealDB&#xff1a;数据驱动&#xff0c;实时协同。用SurrealDB简化你的开发流程- 精选真开源&#xff0c;释放新价值。 概览 SurrealDB&#xff0c;一款专为现代Web应用设计的云原生数据库&#xff0c;以其创新的架构和功能&#xff0c;为开发者提供了一个强大的工具。它整…...

SQL Server查询计划阅读及分析

​​​​​​6.4.5. 查询计划阅读及分析 SQL Server中,SQL语句的查询计划可能会包含多个节点,每个节点除了包含和对应一个操作符外,还包含节点及操作符相关的其他信息,其细节与具体的操作符相关。SQL Server查询计划与Oracle执行计划中,虽然每个节点所包含内容的具体称谓…...

wordpress 地址/凡科网免费建站

1。注册表中的HKEY_LOCAL_MACHINE\SYSTEM\ControlSet002\Enum\USBSTOR中, 罗列了USB移动存储设备的型号 2。注册表中的HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\DeviceClasses\{53f56307-b6bf-11d0-94f2-00a0c91efb8b}\ 3.注册表中的HKEY_LOCAL_MACHINE\SYSTEM\C…...

网站做子页面怎么做的/搜索引擎营销方法有哪些

在下笔写SQL系列文章时&#xff0c;我突然有点懵&#xff0c;因为从某种意义上来说SQL是我熟悉的陌生人。熟悉是因为我和SQL很早就已相遇&#xff0c;回首整个过程&#xff0c;我们经历过浅浅的相知&#xff0c;长长的相忘于江湖&#xff0c;紧接着又是短暂的重逢&#xff0c;然…...

做愛视频网站/设计网站排行榜前十名

参考 文章目录前言小程序应用生命周期App(Object object)小程序页面生命周期Page(Object object)页面页面配置onLoadonHideonPullDownRefresh&#xff1a;onReachBottomonShareAppMessageonPageScrollonResize在手机启用屏幕旋转页面跳转Navigator方法一 可返回方法二 原地销毁…...

wordpress 全部页面500/最新军事头条

datatype是数据类型。C的数据类型包括&#xff1a;整型、字符型、实型或浮点型(单精度和双精度)、枚举类型、数组类型、结构体类型、共用体类型、指针类型和空类型。数据类型关键字&#xff1a;1、short&#xff1a;修饰int&#xff0c;短整型数据&#xff0c;可省略被修饰的in…...

企通互联的网站建设失败/合肥网站快速优化排名

古人云 “读万卷书&#xff0c;行万里路。” 书籍是人类进步的阶梯、培养阅读习惯&#xff0c;当一个人爱上读书的时候&#xff0c;眼睛都是发光的。 在小编看来&#xff0c;学习理念是【先广度后深度】&#xff0c;先把Java知识体系的东西都了解到&#xff0c;工作上先会用&…...

qq空间可以做网站吗/电商seo优化

这里是对docker compose 网络配置的一些说明&#xff0c;详细的文档参考&#xff1a; https://docs.docker.com/compose/networking/ 1 default network 如果不显式指定&#xff0c;Compose会为每一个app设置一个default网络。每个service的container会加入这个default网络并…...