【算法】力扣【树形DP】687. 最长同值路径
【算法】力扣【树形DP】687. 最长同值路径
687. 最长同值路径
文章目录
- 【算法】力扣【树形DP】687. 最长同值路径
- 题目描述
- 输入输出示例
- 题解思路
- 代码描述
- 复杂度分析
- 总结
题目描述
本题要求在给定的二叉树中寻找最长的同值路径,这个路径中的每个节点的值都相同。路径可以通过也可以不通过根节点,路径长度由节点间的边数表示。
其实就是在二叉树的直径的基础上,多考虑了每个节点的值而已。
输入输出示例
-
示例 1:
输入:root = [5,4,5,1,1,5]
输出:2解释: 最长的同值路径为树中的两个值为5的节点之间的路径,路径长度为2。
-
示例 2:
输入:root = [1,4,5,4,4,5]
输出:2解释: 最长的同值路径为树中值为4的两个相邻节点间的路径,或者值为5的两个相邻节点间的路径,路径长度均为2。
题解思路
为了解决这个问题,我们采用树形动态规划的方法。在处理任何一个节点时,我们需要知道以该节点为终点的最长同值路径,并且我们也需要知道经过该节点的最长同值路径长度。这两个信息可以帮助我们递归地求解整棵树。
代码描述
在代码中,我们定义一个递归函数dp,它返回两个值:
- 以当前节点为终点的最长同值路径长度。
- 当前节点的值。
代码中有四种情况需要考虑:
- 左子树和右子树的值与当前节点相同。
- 仅左子树的值与当前节点相同。
- 仅右子树的值与当前节点相同。
- 左右子树的值都与当前节点不同。
我们需要根据这些情况更新答案,并返回适当的值。以下是代码段及注释:
class Solution:def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:def dp(node):if node is None:return 0, -1cval = node.valleft, lval = dp(node.left)right, rval = dp(node.right)nonlocal ans# 情况1:左右子树的值均与当前节点相同if lval == rval == cval:ans = max(ans, left + right)return max(left, right) + 1, cval# 情况2:仅左子树的值与当前节点相同elif lval == cval:ans = max(ans, left)return left + 1, cval# 情况3:仅右子树的值与当前节点相同elif rval == cval:ans = max(ans, right)return right + 1, cval# 情况4:左右子树的值均与当前节点不同else:return 1, cvalans = 0dp(root)return ans
复杂度分析
- 时间复杂度: O ( n ) O(n) O(n),其中 n n n表示节点数量。每个节点仅被访问一次。
- 空间复杂度: O ( n ) O(n) O(n),其中 n n n表示节点的数量,因为在最坏的情况下树会退化成一条链。空间复杂度主要取决于递归时堆栈的深度。
总结
本题是一道中等难度的树形DP问题,通过分治的思想和递归实现,仅仅是在树形DP的外皮上套了一层需求,我们只需要思考一下如何将节点的值考虑进状态转移方程即可非常简单地解决这个问题。
相关文章:
【算法】力扣【树形DP】687. 最长同值路径
【算法】力扣【树形DP】687. 最长同值路径 687. 最长同值路径 文章目录 【算法】力扣【树形DP】687. 最长同值路径题目描述输入输出示例 题解思路代码描述 复杂度分析总结 题目描述 本题要求在给定的二叉树中寻找最长的同值路径,这个路径中的每个节点的值都相同。…...
S32DS用PE调试报错
1、问题: 在S32DS上用PE进行调试报错: Error while launching command: --version 2、解决方法 按下图操作 填入内容: ${cross_prefix}gdb${cross_suffix}...
Day02-DDLDMLDQL(定义,操作,查询)(联合查询,子查询,字符集和校对集,MySQL5.7乱码问题)
文章目录 Day02-DDL&DML和DQL学习目标1. SQL语言的组成2. DDL2.1 数据库结构2.2 表结构2.3 约束2.3.1 主键约束(重要)(1)特点(2) 添加主键(3)删除主键(了解) 2.3.2 自增约束(1)特点(2) 添加自增约束(3)删除自增约束(了解) 2.3.3 非空约束(1)添加非空约束(2) 删除非空约束 2…...
3D高斯泼溅的崛起
沉浸式媒体领域正在以前所未有的速度发展,其中 3D 高斯溅射成为一项关键突破。 这项技术在广泛的应用中看起来非常有前景,并且可能会彻底改变我们未来创建数字环境以及与数字环境交互的方式。 在本文中,我们将通过与摄影测量和 NeRF 等前辈进…...
基于python+vue家政服务系统flask-django-php-nodejs
相比于以前的传统手工管理方式,智能化的管理方式可以大幅降低家政公司的运营人员成本,实现了家政服务的标准化、制度化、程序化的管理,有效地防止了家政服务的随意管理,提高了信息的处理速度和精确度,能够及时、准确地…...
用户中心项目(登录 + 用户管理功能后端)
文章目录 1.登录功能-后端1.思路分析2.完成对用户名和密码的校验1.com/sun/usercenter/service/UserService.java 添加方法2.com/sun/usercenter/service/impl/UserServiceImpl.java 添加方法3.com/sun/usercenter/service/impl/UserServiceImpl.java 新增属性 3.记录用户的登录…...
嵌入式相机WEB,用C直接处理?
以前用HTTP连接相机的时候,以为是相机内部有一个类似tomcat之类的WEB服务器。收到相机命令后,通过链接库执行动作。 昨天想给相机增加一个时间显示,增加的项目一点就跳转到登录。 于是问了之前负责的,说是要后端改。再问嵌入式相…...
LeetCode_31_中等_下一个排列
文章目录 1. 题目2. 思路及代码实现详解(Python)2.1 两遍扫描 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如, a r r [ 1 , 2 , 3 ] arr [1,2,3] arr[1,2,3] ,以下这些都可以视作 a r r arr arr…...
huggingface的transformers训练gpt
目录 1.原理 2.安装 3.运行 编辑 4.数据集 编辑 4.代码 4.1 model init编辑 forward: 总结: 关于loss和因果语言模型: 编辑 交叉熵:编辑 记录一下transformers库训练gpt的过程。 transformers/examples/…...
第六十一回 放冷箭燕青救主 劫法场石秀跳楼-编译安装飞桨paddlepaddle@openKylin+RISCV
卢俊义在水里被张顺抓住,用轿子抬到了梁山。宋江等人下马跪在地上迎接,请他坐第一把交椅。卢俊义宁死不从,大家只好说留他在山寨几天,先让李固带着马车货物回去。吴用对李固说,你的主人已经答应坐第二把交椅了…...
白话讲人工智能、机器学习、深度学习
人工智能(Artificial Intelligence,AI) 定义: 想象一个聪明的机器人,它能思考、决策和学习,就像电影里的智能角色那样。人工智能就是努力打造这样的智能实体的学科,它试图模仿、扩展乃至超越人…...
ssm项目(tomcat项目),定时任务(每天运行一次)相同时间多次重复运行job 的bug
目录标题 一、原因 一、原因 debug本地调试没有出现定时任务多次运行的bug,上传到服务器就出现多次运行的bug。(war的方式部署到tomcat) 一开始我以为是代码原因,或者是linux和win环境不同运行定时任务的方式不一样。 但是自己…...
vue3 + ts +element-plus + vue-router + scss + axios搭建项目
本地环境: node版本:20.10.0 目录 一、搭建环境 二、创建项目 三、修改页面 四、封装路由vue-router 五、element-plus 六、安装scss 七、封装axios 一、搭建环境 1、安装vue脚手架 npm i -g vue/cli 2、查看脚手架版本 vue -V3、切换路径到需…...
二叉树试题解析
一、单项选择题 01.下列关于二叉树的说法中,正确的是( C ). A.度为2的有序树就是二叉树 B.含有n个结点的二叉树的高度为 C.在完全二叉树中,若一个结点没有左孩子,则它必是叶结点 D.含有n个结点的完全二叉树的高度为解析:A 二叉树…...
计算机服务器中了faust勒索病毒怎么办,faust勒索病毒解密工具流程
网络是一把利剑,可以方便企业开展各项工作业务,为企业提供极大的便利,但随着网络技术的不断发展与应用,网络数据安全威胁也在不断增加,给企业的正常生产运营带来了极大困扰,近日,云天数据恢复中…...
初次部署麒麟V10系统需要的配置,快速完成测试环境的搭建
配置麒麟V10 设置“root”登录密码 sudo su -passwd # 设置登录密码允许“root”远程登录 sudo vim /etc/ssh/sshd_configsshd_config # ↓↓↓↓修改的内容↓↓↓↓ PermitRootLogin yes # ↑↑↑↑修改的内容↑↑↑↑重启服务 sudo systemctl restart sshd允许通过图像界…...
DOcker in Docker 原理与实战代码详解
Docker in Docker(DinD)指的是在Docker容器内部运行另一个Docker守护进程和客户端。这种技术可以用于创建嵌套的Docker环境,例如在持续集成/持续部署(CI/CD)管道中构建和测试Docker镜像。然而,需要注意的是…...
公司系统中了.rmallox勒索病毒如何恢复数据?
早晨上班时刻: 当阳光逐渐洒满大地,城市的喧嚣开始涌动,某公司的员工们纷纷踏入办公大楼,准备开始新的一天的工作。他们像往常一样打开电脑,准备接收邮件、查看日程、浏览项目进展。 病毒悄然发作: 就在员…...
论文阅读:Forget-Me-Not: Learning to Forget in Text-to-Image Diffusion Models
Forget-Me-Not: Learning to Forget in Text-to-Image Diffusion Models 论文链接 代码链接 这篇文章提出了Forget-Me-Not (FMN),用来消除文生图扩散模型中的特定内容。FMN的流程图如下: 可以看到,FMN的损失函数是最小化要消除的概念对应的…...
html5cssjs代码 036 CSS默认值
html5&css&js代码 036 CSS默认值 一、代码二、解释 CSS默认值(也称为浏览器默认样式)是指当HTML元素没有应用任何外部CSS样式时,浏览器自动为这些元素赋予的一组基本样式。这些样式是由浏览器的默认样式表(User Agent sty…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...
