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

力扣labuladong——一刷day61

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、力扣865. 具有所有最深节点的最小子树
  • 二、力扣1123. 最深叶节点的最近公共祖先
  • 三、力扣1026. 节点与其祖先之间的最大差值
  • 四、力扣1120. 子树的最大平均值


前言


二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「分解问题」的思维,而且涉及处理子树,需要用后序遍历

一、力扣865. 具有所有最深节点的最小子树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode subtreeWithAllDeepest(TreeNode root) {Result res = fun(root);return res.node;}public Result fun(TreeNode root){if(root == null){return new Result(null,0);}Result left = fun(root.left);Result right = fun(root.right);if(left.depth == right.depth){return new Result(root,left.depth+1);}Result res = left.depth > right.depth ? left : right;res.depth = res.depth + 1;return res;}
}
class Result{public TreeNode node;public int depth;public Result(TreeNode node, int depth){this.node = node;this.depth = depth;}
}

二、力扣1123. 最深叶节点的最近公共祖先

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode lcaDeepestLeaves(TreeNode root) {Result res = fun(root);return res.node;}public Result fun(TreeNode root){if(root == null){return new Result(null,0);}Result left = fun(root.left);Result right = fun(root.right);if(left.depth == right.depth){return new Result(root,left.depth+1);}Result res = left.depth > right.depth ? left : right;res.depth = res.depth + 1;return res;}
}
class Result{public TreeNode node;public int depth;public Result(TreeNode node, int depth){this.node = node;this.depth = depth;}
}

三、力扣1026. 节点与其祖先之间的最大差值

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = 0;public int maxAncestorDiff(TreeNode root) {fun(root);return res;}public int[] fun(TreeNode root){if(root == null){return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};}int[] leftMinMax = fun(root.left);int[] rightMinMax = fun(root.right);int curMin = Math.min(Math.min(leftMinMax[0],rightMinMax[0]),root.val);int curMax = Math.max(Math.max(leftMinMax[1],rightMinMax[1]),root.val);res = Math.max(res,Math.max(curMax - root.val, root.val - curMin));return new int[]{curMin,curMax};}
}

四、力扣1120. 子树的最大平均值

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {double res = 0;public double maximumAverageSubtree(TreeNode root) {fun(root);return res;}public double[] fun(TreeNode root){if(root == null){return new double[]{0,0};}double[] left = fun(root.left);double[] right = fun(root.right);double curCount = left[0] + right[0] + 1;double curSum = left[1] + right[1] + root.val;res = Math.max(res,curSum/curCount);if(curCount == 1){return new double[]{curCount,root.val};}return new double[]{curCount,curSum};}
}

相关文章:

力扣labuladong——一刷day61

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣865. 具有所有最深节点的最小子树二、力扣1123. 最深叶节点的最近公共祖先三、力扣1026. 节点与其祖先之间的最大差值四、力扣1120. 子树的最大平均值 …...

nacos配置变更导致logback日志异常

问题背景: 线上的服务突然内存爆满,查服务器突然发现,日志全部打印到了/tmp/tomcat.xxx.port目录下,后来对应操作时间,和nacos修改配置是同一时间发生的,但是疑惑的点是,nacos配置变更为什么会引起logback的…...

【spring(五)】SpringMvc总结 SSM整合流程

目录 一、SpringMVC简介: 二、SpringMVC快速入门: 三、SpringMVC bean的管理:⭐ ①配置bean ②扫描bean 四、SpringMVC配置类:⭐ 五、SpringMVC 请求与响应 六、SpringMVC REST风格 七、SSM整合 异常处理: 八、…...

1、windows10系统下Qt5.12.0与卸载

一、安装包下载 1、Qt社区下载 https://download.qt.io/archive/qt/5.12/5.12.10/qt-opensource-windows-x86-5.12.10.exe 2、百度网盘下载 链接:百度网盘 请输入提取码 3、Qt官网下载: Try Qt | 开发应用程序和嵌入式系统 | Qt 二、安装提示 下…...

WebGL/threeJS面试题扫描与总结

什么是 WebGL?什么是 Three.js?请解释three.js中的WebGL和Canvas的区别? WebGL(全写Web Graphics Library)是一种3D绘图协议,这种绘图技术标准允许把JavaScript和OpenGL ES 2.0结合在一起,通过增加OpenGL ES 2.0的一个…...

Qt connect()方法Qt::ConnectionType

connect() Qt,绑定信号和槽原型: static QMetaObject::Connection connect(const QObject *sender, const char *signal,const QObject *receiver, const char *member, Qt::ConnectionType Qt::AutoConnection);static QMetaObject::Connection conn…...

HIVE SQL时间函数

目录 current_timestamp()获取当前时间unix_timestamp()获取当前时区的UNIX时间戳from_unixtime()时间戳转日期函数unix_timestamp(string date)日期转时间戳函数提取日期中的年月日时分秒weekofyear (string date)日期转周函数日期比较函数datediff(string enddate, string st…...

linux磁盘的LVM、交换分区以及文件系统

目录 逻辑卷LVM LVM管理 LVM特点 LVM的制作 创建物理卷 创建卷组 创建逻辑卷 格式化文件系统 挂载逻辑卷 LVM的扩容 添加硬盘做物理卷 卷组扩容 扩容逻辑卷 给文件系统扩容 LVM移除 LVM的缩容 交换分区 查看当前交换分区:free Swap:虚…...

【HDFS】ActiveNamenodeResolver#getNamespaces 方法调用点梳理

获取所有的注册在router里的active状态的集群。 /*** Get a list of all namespaces that are registered and active in the* federation.** @return List of name spaces in the federation* @throws IOException Throws exception if the namespace list is not* av…...

算法—双指针

双指针算法可以帮忙把时间复杂度降低一个维度,即原本O(n2)降为O(n);将O(n)降为O(1) 移动零 移动零 题目解析 将所有0移动到末尾保持非0元素相对顺序对数组进行原地操作(不开辟额外空间) 算法原理 数组…...

​[Oracle]编写程序,键盘输入n,计算1+前n项之和。测试案例:输入:10 输出:22.47​

编写程序,键盘输入n,计算1前n项之和。 测试案例: 输入:10 输出:22.47 代码如下: set serveroutput on declare v_sum number:0;v_n number;beginv_n:&n;for i in 1..v_n loopv_sum:v_sumsqrt(i); end loop; d…...

【视觉SLAM十四讲学习笔记】第三讲——旋转向量和欧拉角

专栏系列文章如下: 【视觉SLAM十四讲学习笔记】第一讲——SLAM介绍 【视觉SLAM十四讲学习笔记】第二讲——初识SLAM 【视觉SLAM十四讲学习笔记】第三讲——旋转矩阵 本章将介绍视觉SLAM的基本问题之一:如何描述刚体在三维空间中的运动? 旋转向…...

【UGUI】制作用户注册UI界面

这里面主要的操作思想就是 1.打组 同一个事情里面包含两个UI元素都应该打组便于管理和查找 2.设置锚点位置 每次创建一个UI都应该设置他的锚点以便于跟随画布控制自己的:相对位置 3. 设置尺寸(像素大小) 每一次UI元素哪怕是作为父物体的…...

【UE】透视效果

效果 步骤 1. 新建一个空白工程 2. 添加一个第三人称游戏和初学者内容包到内容浏览器 3. 新建一个材质,这里命名为“M_Perspective” 打开“M_Perspective”,设置材质域为后期处理 添加三个“SceneTexture”节点,场景纹理ID选项分别设置为“…...

前端下载文件或者图片方式,window.open或者a标签形式

首先分别讲一下下载文件的方式都有哪些 1.通过a标签的方式下载文件 <a href"http://www.baidu.com" download"baidu.html">下载</a> 我们点击下载&#xff0c;发现是跳转到了百度的首页&#xff0c;并没有真的下载文件。 因为a标签下载只能…...

webpack配置scss loader

国内GPT站点&#xff1a;https://www.atalk-ai.com 在 Webpack 中配置 sass-loader 用于处理 .scss 文件通常涉及以下步骤&#xff1a; 安装必要的依赖&#xff1a; 你需要安装 sass-loader&#xff0c;以及 sass 本身&#xff08;sass 是 node-sass 的替代品&#xff0c;更快且…...

k8s有状态部署mysql主从(local pv持久化)

1、修改自己对应的命名空间 2、local pv的方式必须先创建好目录在给权限 3、sts部署文件密码都要修改好在部署 yaml资源文件如下&#xff1a; #配置mysql的root密码再部署&#xff0c;如果部署了在修改root密码就会失败&#xff0c;必须在初始化就把root密码修改好 #部署采…...

下载并安装anaconda和VScode,配置虚拟环境,并使用VScode运行代码

文章目录 前言软件下载Anaconda下载VScode下载 软件安装Anaconda安装Vscod安装 配置虚拟环境并运行代码Anaconda创建环境VScode使用&#xff0c;运行代码1. 打开代码所在文件夹2. 选择解释器3. 运行代码 总结 前言 运行python代码&#xff0c;需要2个软件如下&#xff1a; Ana…...

拼图 游戏

运行出的游戏界面如下&#xff1a;按住A不松开&#xff0c;显示完整图片&#xff1b;松开A显示随机打乱的图片 User类 package domain;/*** ClassName: User* Author: Kox* Data: 2023/2/2* Sketch:*/ public class User {private String username;private String password;p…...

python循环语句和函数

1.使用for循环打印9*9乘法表 for i in range(1, 10):for j in range(1, i1):print(i, "*", j, "", i*j, end"\t")print()结果&#xff1a; 2.使用while循环打印9*9乘法表 i 1 while i < 10:j 1while j < i1:print(i, "*", j…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...