代码随想录 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;}

相关文章:
代码随想录 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%B…...
降雨量预测 | Matlab基于ARIMA-RBF降雨量预测
目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 降雨量预测 | Matlab基于ARIMA-RBF降雨量预测 注:程序和数据放在一个文件夹。 程序语言为matlab,程序可出预测效果图,指标图; 代码特点:参数化编程、参数可方便更改、代…...
包含示例和模板的流程文档指南
当您的业务扩展时,您会得到越来越多的移动部件,并且需要有人来跟踪复杂性。人员和任务需要以尽可能最高效的方式进行组织,并且您必须找到某种方法让员工知道如何执行有效完成工作所需的流程。 为了使流程可重复,需要对其进行记录…...
51单片机嵌入式开发:15、STC89C52RC操作蜂鸣器实现一个music音乐播放器的音乐盒
STC89C52RC操作蜂鸣器实现一个music音乐播放器的音乐盒 1 概述2 蜂鸣器操作方法3 蜂鸣器发出音声4 硬件电路5 软件实现6 整体工程:7 总结 1 概述 要实现一个基于STC89C52RC单片机的音乐盒,可以按照以下步骤进行: (1)硬…...
B树(B-Tree)数据结构
1. 什么是B树? B树(B-Tree)是一种多路搜索树,用于存储和检索大量数据。它是自适应的,适用于各种存储设备和各种数据量。B树的特点是高效的搜索、插入和删除操作,且可以在各种情况下保持树的平衡。 2. B树…...
【BUG】已解决:ModuleNotFoundError: No module named ‘torch‘
已解决:ModuleNotFoundError: No module named ‘torch‘ 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科班出身,就职于医疗科技公司,热衷分享知识,武汉城市…...
数据结构——队列(链式结构)
一、队列链式结构定义 队列的链式存储结构是一种用链表实现的队列,它不像顺序存储结构那样需要预先分配固定大小的空间。链式存储结构的队列由节点组成,每个节点包括数据和指向下一个节点的指针。队列的链式存储结构可以动态地分配内存,更灵活地处理数据。在链式存储结构中…...
解决GoLand添加GOROOT提示The selected directory is not a valid home for Go Sdk的问题
现象 解决 在Go安装路径下找到zversion.go文件,我的在D:\Program Files\Go1.21.1\src\runtime\internal\sys下面 打开文件,添加如下内容: 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. 实物连接图:STC8H8K64URA8889开发板,使用P2口I2C接口: 2.实物连…...
【Python其他检查字符串占字节数的方法】
在Python中,检查字符串在特定编码下占用的字节数,最标准且常用的方法是通过字符串的.encode()方法将字符串转换为字节串,然后使用len()函数来获取这个字节串的长度。这是因为字符串(在Python 3中)是以Unicode形式存储的…...
梧桐数据库: 数据库技术中的重写子查询技术
数据库技术中的重写子查询技术,是数据库查询优化的一种重要手段。该技术主要通过改变子查询的形式,使其在执行效率和性能上得到优化。以下是对重写子查询技术的详细解析: 一、定义与目的 定义:重写子查询技术是指在数据库查询优…...
PHP连接MySQL数据库
PHP本身不具备操作MySQL数据库的能力,需要借助MySQL扩展来实现。 1、PHP加载MySQL扩展:php.ini文件中。(不要用记事本打开) 2、PHP中所有扩展都是在ext的文件夹中,需要指定扩展所在路径:extension_dir。 3、…...
STM32自己从零开始实操:PCB全过程
一、PCB总体分布 以下只能让大家看到各个模块大致分布在板子的哪一块,只能说每个人画都有自己的理由: 电源:从外部接入电源,5V接到中间,向上变成4V供给无线,向下变成3V供给下面的接口(也刻意放…...
error `slot` attributes are deprecated vue/no-deprecated-slot-attribute
旧的代码如下: <template slot"title">{{ item.title }}</template> {{ item.title }} 是一个模板标签,它在模板中插入了一个元素(slot),并指定了元素的名称为 “title”。这个标签在模板中显示…...
Websocket自动消息回复服务端工具
点击下载《Websocket自动消息回复服务端工具》 1. 前言 在进行Websocket开发时,前端小伙伴通常是和后端开发人员同步进行项目开发,经常会遇到后端开发人员接口还没开发完,也没有可以调试的环境,只能按照接口文档进行“脑回路开发…...
【软考】UML中的关联关系
目录 一、说明二、具体类型2.1 普通关联2.2 单向关联2.3 双向关联2.4 自关联2.4 聚合关系(Aggregation)2.5 组合关系(Composition) 三、关联关系中的多重性 一、说明 1.UML(Unified Modeling Language,统一…...
贪吃蛇超精讲(C语言)
前言 如果你还是个萌新小白,那么该项目的攻克过程一定会十分艰难。虽然作者已经将文章尽可能写的逻辑清晰,内容详细。但所谓“纸上得来终觉浅”,在讲到陌生结构和函数时,大家请一定自己动手去敲一遍代码,这很重要&…...
掌握Rust:函数、闭包与迭代器的综合运用
掌握Rust:函数、闭包与迭代器的综合运用 引言:解锁 Rust 高效编程的钥匙函数定义与模式匹配:构建逻辑的基石高阶函数与闭包:代码复用的艺术迭代器与 for 循环:高效数据处理的引擎综合应用案例:构建一个简易…...
【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搭建教程 全开源版的教程,其他未知 资源宝整理分享 www.httple.net 首先ssh执行指令安装运行环境 yum install java-1.8.0-openjdk* -y导入文件服务器 导入arm.zip到www目录下然后解压 导入jar包.zip到www目录然后解压 导入basic.zip到www目录然后解压在宝塔…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...
Excel 怎么让透视表以正常Excel表格形式显示
目录 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总...
LeetCode - 148. 排序链表
目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣(LeetCode) 思路 链表归并排序采用"分治"的策略,主要分为三个步骤: 分割:将链表从中间…...
