leetcode687. 最长同值路径(java)
最长同值路径
- 题目描述
- DFS 深度遍历
- 代码演示
题目描述
难度 - 中等
LC - 687. 最长同值路径
给定一个二叉树的 root ,返回 最长的路径的长度 ,这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例1:
输入:root = [5,4,5,1,1,5]
输出:2
示例2:
输入:root = [1,4,5,4,4,5]
输出:2
提示:
树的节点数的范围是 [0, 104]
-1000 <= Node.val <= 1000
树的深度将不超过 1000
DFS 深度遍历
设计递归函数 int dfs(TreeNode root),含义为传入根节点 root,返回以该节点为起点,往下走同值路径所能经过的最大路径长度(即不能同时往左右节点走),同时使用全局变量 max 记录答案路径所能经过最大路径长度。
在递归函数内部,先通过递归 root 的左右子节点,拿到以 root.left 和 root.right 为起点的最大路径长度 l 和 r,然后根据当前节点值和左右子节点值的相等关系来更新 ans,同时用 cur 维护「以当前节点 root 为目标路径中深度最小(位置最高)节点时」所经过的最大路径长度。
代码演示
/*** 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 ans;public int longestUnivaluePath1(TreeNode root) {ans = 0;dfs(root);return ans;}int dfs(TreeNode root){if(root == null){return 0;}int left = dfs(root.left);int right = dfs(root.right);//left1 right1 来记录左右节点和头节点的连接情况int left1 = 0, right1 = 0;//如果左边节点和root 相等,left1 + 1,就连接起来了if(root.left != null && root.left.val == root.val){left1 = left + 1;}//同上if(root.right != null && root.right.val == root.val){right1 = right + 1;}//记录最大值,如果左右节点都相等,两个值相加ans = Math.max(ans,left1 + right1);return Math.max(left1,right1);}
}
相关文章:
leetcode687. 最长同值路径(java)
最长同值路径 题目描述DFS 深度遍历代码演示 题目描述 难度 - 中等 LC - 687. 最长同值路径 给定一个二叉树的 root ,返回 最长的路径的长度 ,这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。 两个节点之间的路径长度 由它们之…...
MySQL的常用术语
目录 1.关系 2.元组 3.属性 MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 1.关系 前面的博客有说到,MySQL是一款关系型数据库管理软件,一个关系就是 一张二维表(表) 我想大家都知道表格怎么…...
机器学习的特征工程
字典特征提取 def dict_demo():"""字典特征提取:return:"""data [{city: 北京, temperature: 100}, {city: 上海, temperature: 60}, {city: 深圳, temperature: 30}]# data [{city:[北京,上海,深圳]},{temperature:["100","6…...
python3 修改nacos的yaml配置
一、安装nacos库 pip install nacos-sdk-python 二、代码如下 import nacos import yaml# 连接地址 NACOS_SERVER_ADDRESSES "192.168.xx.xx" NACOS_SERVER_PORT 替换为你的端口号,如8848# 命名空间 NACOS_NAMESPACE "your_namespace"# 账…...
YOLOv8 : 数据组织
1. 数据源 首先YOLOv8是支持目标分类、检测和目标分割。当前以应用最为广泛的目标检测为例,简单说明数据相关的信息。 一般情况下,建议将数据划分成images和labels,其中images存储图像,labels存储标签文件(YOLO格式)。如果是VOC数…...
golang如何生成zip压缩文件
在Golang中,您可以使用标准库中的compress/zip包来生成ZIP压缩文件。下面是一个简单的示例代码,演示如何使用该包来创建一个ZIP文件并将文件添加到其中: package main import ( "archive/zip" "bytes" "fmt&qu…...
AntDesign技术指南:构建优雅的前端界面
引言 AntDesign是一款优秀的前端UI组件库,它提供了丰富的组件和功能,帮助我们快速构建漂亮、易用的前端界面。本篇博客将详细介绍AntDesign的使用方法和技巧,并展示完整的代码示例。无论你是初学者还是有经验的开发者,本篇博客都…...
机器人任务挖掘与智能超级自动化技术解析
本文为上海财经大学教授、安徽财经大学学术副校长何贤杰出席“会计科技Acctech应对不确定性挑战”高峰论坛时的演讲内容整理。何贤杰详细介绍了机器人任务挖掘与智能超级自动化技术的发展背景、关键技术和应用场景。 从本质来说,会计是非常适合智能化、自动化的。会…...
C#通过ModbusTcp协议读写西门子PLC中的浮点数
一、Modbus TCP通信概述 MODBUS/TCP是简单的、中立厂商的用于管理和控制自动化设备的MODBUS系列通讯协议的派生产品,显而易见,它覆盖了使用TCP/IP协议的“Intranet”和“Internet”环境中MODBUS报文的用途。协议的最通用用途是为诸如PLC,I/…...
19-springcloud(中)
一 服务注册发现 1 什么是服务治理 为什么需要服务治理 在没有进行服务治理前,服务之间的通信是通过服务间直接相互调用来实现的。 过程: 武当派直接调用峨眉派和华山派,同样,华山派直接调用武当派和峨眉派。如果系统不复杂,这样…...
Leetcode1090. 受标签影响的最大值
思路:根据值从大到小排序,然后在加的时候判断是否达到标签上限即可,一开始想用字典做,但是题目说是集合却连续出现两个8,因此使用元组SortedList进行解决 class Solution:def largestValsFromLabels(self, values: li…...
第七章:敏捷开发工具方法-part2-CI/CD工具介绍
文章目录 前言一、CI-持续集成1.1 安装部署gitlab 二、gitlab CI配置三、jenkins实现CI / CD3.1 安装jenkins3.2 配置CI3.3 配置CD3.4 其他构建方式1、定时构建2、指定参数构建3、webhook自动根据git事件进行构建 前言 什么是CI/Cd? CI-Continuous integration&…...
【自学开发之旅】Flask-回顾--对象拆分-蓝图(二)
url-统一资源定位符-不同的url对应不同的资源 作为服务端,url和视图函数的映射关系就是路由。 定义传递参数的方式: 1.创建动态url app.route("/login2/<username>/<passwd>") def login2(username, passwd):if username "…...
自动驾驶中间件
自动驾驶中间件 1. 什么是中间件2. 中间件的分类3. 自动驾驶为什么需要中间件4. 通信中间件 Reference: 自动驾驶中间件:量产落地的关键技术通俗易懂的告诉你什么是中间件 对于初入自动驾驶行业的人来说,各色各样的新型传感器、线控系统、芯…...
鲲鹏920(ARM64)移植javacpp
JavaCPP JavaCPP 使得Java 应用可以在高效的访问本地C++方法,JavaCPP底层使用了JNI技术,可以广泛的用在Java SE应用中(也包括安卓),以下两个特性是JavaCPP的关键,稍后咱们会用到: 提供一些注解,将Java代码映射为C++代码提供一个jar,用java -jar命令可以将C++代码转为…...
python打包exe实用版
pyinstaller模块用于将python项目打包成exe文件,以方便地在没有安装python环境的机器上运行。该模块使用 pip install pyinstaller 安装即可。 参数命令含义-Dpyinstaller -D demo.py默认选项。除了主程序demo.exe外,还会在在dist文件夹中生成很多依赖文…...
什么是反向代理(Reverse Proxy)?解释反向代理的作用和常见应用。
1、什么是反向代理(Reverse Proxy)?解释反向代理的作用和常见应用。 反向代理是一种代理服务器模型,它位于客户端和后端服务器之间。它允许将请求转发到后端服务器,并将响应返回给客户端。反向代理的主要作用如下&…...
算法通关村第十二关——不简单的字符串转换问题
前言 字符串是我们在日常开发中最常处理的数据,虽然它本身不是一种数据结构,但是由于其可以包含所有信息,所以通常作为数据的一种形式出现,由于不同语言创建和管理字符串的方式也各有差异,因此针对不同语言特征又产生…...
PROSOFT PTQ-PDPMV1网络接口模块
通信接口:PROSOFT PTQ-PDPMV1 网络接口模块通常配备了多种通信接口,以便与不同类型的设备和网络进行通信。常见的接口包括以太网、串行端口(如RS-232和RS-485)、Profibus、DeviceNet 等。 协议支持:该模块通常支持多种…...
力扣(LeetCode)算法_C++——稀疏矩阵的乘法
给定两个 稀疏矩阵 :大小为 m x k 的稀疏矩阵 mat1 和大小为 k x n 的稀疏矩阵 mat2 ,返回 mat1 x mat2 的结果。你可以假设乘法总是可能的。 示例 1: 输入:mat1 [[1,0,0],[-1,0,3]], mat2 [[7,0,0],[0,0,0],[0,0,1]] 输出&am…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

输入:root = [5,4,5,1,1,5]
输入:root = [1,4,5,4,4,5]