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

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 &#xff0c;返回 最长的路径的长度 &#xff0c;这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。 两个节点之间的路径长度 由它们之…...

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 替换为你的端口号&#xff0c;如8848# 命名空间 NACOS_NAMESPACE "your_namespace"# 账…...

YOLOv8 : 数据组织

1. 数据源 首先YOLOv8是支持目标分类、检测和目标分割。当前以应用最为广泛的目标检测为例&#xff0c;简单说明数据相关的信息。 一般情况下&#xff0c;建议将数据划分成images和labels&#xff0c;其中images存储图像&#xff0c;labels存储标签文件(YOLO格式)。如果是VOC数…...

golang如何生成zip压缩文件

在Golang中&#xff0c;您可以使用标准库中的compress/zip包来生成ZIP压缩文件。下面是一个简单的示例代码&#xff0c;演示如何使用该包来创建一个ZIP文件并将文件添加到其中&#xff1a; package main import ( "archive/zip" "bytes" "fmt&qu…...

AntDesign技术指南:构建优雅的前端界面

引言 AntDesign是一款优秀的前端UI组件库&#xff0c;它提供了丰富的组件和功能&#xff0c;帮助我们快速构建漂亮、易用的前端界面。本篇博客将详细介绍AntDesign的使用方法和技巧&#xff0c;并展示完整的代码示例。无论你是初学者还是有经验的开发者&#xff0c;本篇博客都…...

机器人任务挖掘与智能超级自动化技术解析

本文为上海财经大学教授、安徽财经大学学术副校长何贤杰出席“会计科技Acctech应对不确定性挑战”高峰论坛时的演讲内容整理。何贤杰详细介绍了机器人任务挖掘与智能超级自动化技术的发展背景、关键技术和应用场景。 从本质来说&#xff0c;会计是非常适合智能化、自动化的。会…...

C#通过ModbusTcp协议读写西门子PLC中的浮点数

一、Modbus TCP通信概述 MODBUS/TCP是简单的、中立厂商的用于管理和控制自动化设备的MODBUS系列通讯协议的派生产品&#xff0c;显而易见&#xff0c;它覆盖了使用TCP/IP协议的“Intranet”和“Internet”环境中MODBUS报文的用途。协议的最通用用途是为诸如PLC&#xff0c;I/…...

19-springcloud(中)

一 服务注册发现 1 什么是服务治理 为什么需要服务治理 在没有进行服务治理前,服务之间的通信是通过服务间直接相互调用来实现的。 过程&#xff1a; 武当派直接调用峨眉派和华山派&#xff0c;同样&#xff0c;华山派直接调用武当派和峨眉派。如果系统不复杂&#xff0c;这样…...

Leetcode1090. 受标签影响的最大值

思路&#xff1a;根据值从大到小排序&#xff0c;然后在加的时候判断是否达到标签上限即可&#xff0c;一开始想用字典做&#xff0c;但是题目说是集合却连续出现两个8&#xff0c;因此使用元组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&#xff1f; CI-Continuous integration&…...

【自学开发之旅】Flask-回顾--对象拆分-蓝图(二)

url-统一资源定位符-不同的url对应不同的资源 作为服务端&#xff0c;url和视图函数的映射关系就是路由。 定义传递参数的方式&#xff1a; 1.创建动态url app.route("/login2/<username>/<passwd>") def login2(username, passwd):if username "…...

自动驾驶中间件

自动驾驶中间件 1. 什么是中间件2. 中间件的分类3. 自动驾驶为什么需要中间件4. 通信中间件 Reference&#xff1a; 自动驾驶中间件&#xff1a;量产落地的关键技术通俗易懂的告诉你什么是中间件 对于初入自动驾驶行业的人来说&#xff0c;各色各样的新型传感器、线控系统、芯…...

鲲鹏920(ARM64)移植javacpp

JavaCPP JavaCPP 使得Java 应用可以在高效的访问本地C++方法,JavaCPP底层使用了JNI技术,可以广泛的用在Java SE应用中(也包括安卓),以下两个特性是JavaCPP的关键,稍后咱们会用到: 提供一些注解,将Java代码映射为C++代码提供一个jar,用java -jar命令可以将C++代码转为…...

python打包exe实用版

pyinstaller模块用于将python项目打包成exe文件&#xff0c;以方便地在没有安装python环境的机器上运行。该模块使用 pip install pyinstaller 安装即可。 参数命令含义-Dpyinstaller -D demo.py默认选项。除了主程序demo.exe外&#xff0c;还会在在dist文件夹中生成很多依赖文…...

什么是反向代理(Reverse Proxy)?解释反向代理的作用和常见应用。

1、什么是反向代理&#xff08;Reverse Proxy&#xff09;&#xff1f;解释反向代理的作用和常见应用。 反向代理是一种代理服务器模型&#xff0c;它位于客户端和后端服务器之间。它允许将请求转发到后端服务器&#xff0c;并将响应返回给客户端。反向代理的主要作用如下&…...

算法通关村第十二关——不简单的字符串转换问题

前言 字符串是我们在日常开发中最常处理的数据&#xff0c;虽然它本身不是一种数据结构&#xff0c;但是由于其可以包含所有信息&#xff0c;所以通常作为数据的一种形式出现&#xff0c;由于不同语言创建和管理字符串的方式也各有差异&#xff0c;因此针对不同语言特征又产生…...

PROSOFT PTQ-PDPMV1网络接口模块

通信接口&#xff1a;PROSOFT PTQ-PDPMV1 网络接口模块通常配备了多种通信接口&#xff0c;以便与不同类型的设备和网络进行通信。常见的接口包括以太网、串行端口&#xff08;如RS-232和RS-485&#xff09;、Profibus、DeviceNet 等。 协议支持&#xff1a;该模块通常支持多种…...

力扣(LeetCode)算法_C++——稀疏矩阵的乘法

给定两个 稀疏矩阵 &#xff1a;大小为 m x k 的稀疏矩阵 mat1 和大小为 k x n 的稀疏矩阵 mat2 &#xff0c;返回 mat1 x mat2 的结果。你可以假设乘法总是可能的。 示例 1&#xff1a; 输入&#xff1a;mat1 [[1,0,0],[-1,0,3]], mat2 [[7,0,0],[0,0,0],[0,0,1]] 输出&am…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...