树形dp,LeetCode 2385. 感染二叉树需要的总时间

一、题目

1、题目描述

给你一棵二叉树的根节点 root ,二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟,感染 将会从值为 start 的节点开始爆发。

每分钟,如果节点满足以下全部条件,就会被感染:

  • 节点此前还没有感染。
  • 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数

2、接口描述

python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        
    }
};

3、原题链接

2385. 感染二叉树需要的总时间


二、解题报告

1、思路分析

答案很明显就是求start向上最大距离和向下最大距离中大的那个

这个还是很好求的,我们可以两次dfs,开两个数组记录下值,就是一个换根dp,换根到start的时候就返回答案即可

不过更优雅的做法是,我们发现答案来自两部分:start向下最大距离,根节点到start的距离加上从另一颗子树向下的最大距离

那么实际上我们进行一次dfs即可

如果找到start或者子树中找到start,我们向上返回深度的时候就返回到达start的距离

如果没找到,就返回到最远子节点的距离的相反数

2、复杂度

时间复杂度: O(n) 空间复杂度:O(n)

3、代码详解

python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        ret = 0
        def dfs(rt: Optional[TreeNode]) -> int:
            if rt is None:
                return 0
            L = dfs(rt.left)
            R = dfs(rt.right)
            nonlocal ret
            if rt.val == start:
                ret = max(ret, -min(L, R))
                return 1
            if L > 0 or R > 0:
                ret = max(ret, abs(L) + abs(R))
                return max(L, R) + 1
            return min(L, R) - 1
        dfs(root)
        return ret

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
int ret, start;
    int dfs(TreeNode* root){
        if(!root) return 0;
        int L = dfs(root->left), R = dfs(root->right);
        if(root->val == start){
            ret = -min(L, R);
            return 1;
        }
        if(L > 0 || R > 0){
            ret = max(ret, abs(L) + abs(R));
            return max(L, R) + 1;
        }
        return min(L, R) - 1;
    }
    int amountOfTime(TreeNode* root, int start) {
        ret = 0, this->start = start;
        dfs(root);
        return ret;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/569291.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

误差的一阶和二阶——MSE/MAE

variance和bias MSE之前,先看两个更为朴素的指标:variance和bias。 在打靶中,有的人所有的子弹都离靶心很远,偏差显然过高,但是很稳定地维持在某一点附近;有的人平均环数更高,但是分布太过分散…

网络安全之SQL注入漏洞复现(中篇)(技术进阶)

目录 一,报错注入 二,布尔盲注 三,sleep延时盲注 四,DNSlogs 盲注 五,二次注入 六,堆叠注入 总结 一,报错注入 报错注入就是在错误信息中执行 sql 语句,利用网站的报错信息来带…

2024-04-23 linux 查看内存占用情况的命令free -h和cat /proc/meminfo

一、要查看 Linux 系统中的内存占用大小,可以使用 free 命令或者 top 命令。下面是这两个命令的简要说明: 使用 free 命令: free -h这将显示系统当前的内存使用情况,包括总内存、已用内存、空闲内存以及缓冲区和缓存的使用情况。…

使用 Flutter 打造引人入胜的休闲游戏体验

作者 / Zoey Fan 去年,Flutter 休闲游戏工具包进行了一次重大更新。近期在旧金山举办的游戏开发者大会 (GDC) 上,Flutter 首次亮相。GDC 是游戏行业的顶级专业盛会,致力于帮助游戏开发者不断提升开发技能。欢迎您继续阅读,了解开发…

小程序AI智能名片商城系统如何依赖CPM、CPC、CPS技术应用进行营销

在数字化营销的新纪元中,小程序AI智能名片商城系统以其高效、智能的特性,成为了企业营销的重要工具。而CPM、CPC、CPS这三种技术应用,更是为该系统赋予了强大的营销能力。接下来,我们将通过详细的例子,探讨这些技术是如…

微信小程序webview和小程序通讯

1.背景介绍 1.1需要在小程序嵌入vr页面,同时在vr页面添加操作按钮与小程序进行通信交互 1.2 开发工具:uniapp开发小程序 1.3原型图 功能:.点击体验官带看跳转小程序的体验官带看页面 功能:点击立即咨询唤起小程序弹窗打电话 2.…

力扣数据库题库学习(4.23日)

610. 判断三角形 问题链接 解题思路 题目要求:对每三个线段报告它们是否可以形成一个三角形。以 任意顺序 返回结果表。 对于三个线段能否组成三角形的判定:任意两边之和大于第三边,对于这个表内的记录,要求就是(x…

【C语言】指针篇-一篇搞定不同类型指针变量-必读指南(3/5)

男儿不展风云志,空负天生八尺躯。——《警世通言卷四十》🌈个人主页:是店小二呀 🌈C语言笔记专栏:C语言笔记 🌈C笔记专栏: C笔记 🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅 上篇…

vue项目启动npm install和npm run serve时出现错误Failed to resolve loader:node-sass

1.常见问题 问题1:当执行npm run serve时,出现Failed to resolve loader: node-sass,You may need to install it 解决方法: npm install node-sass4.14.1问题2:当执行npm run serve时,出现以下错误 Fa…

ADC内部运行原理

1以一个简单的外置ADC为例讲解 1在外部由地址锁存和译码经行去控制通道选择开关//去控制外部那一条IO口输入,输入到比较器 2逐次逼近寄存器SAR每次从三态锁存缓冲器读取值在由DAC(数模转换成模拟电压)在输入到比较器当io信号和DAC信号几乎一样…

JWT原理解析

一、概述 虽然现在很多的开发框架会支持JWT的使用,但是对JWT还是没有一个详细的了解,有很多疑惑: JWT比之前的session或者token有什么好处?JWT的构成元素是什么?JWT从生成到使用的详细流程? 二、 JWT 2…

华为数通方向HCIP-DataCom H12-821题库(多选题:321-340)

第321题 关于OSPF的命令描述,不正确的是: A、stub区域和totally stub区域配置了no-summary参数 B、OSPFv2和OSPF v3配置接口命令的区别是OSPF V2可以使用network命令,而OSPFv3直接 C、在接口上使能stubrouter命令用来配置次路由器为stub路由器,stub路由器可以与非stub路由 …

AUTOSAR-COMStack-003_SignalGroup如何发送接收

1. Ref Ref.1 AUTOSAR_RS_Main.pdf Ref.1 AUTOSAR_RS_Features.pdf Ref.2 AUTOSAR_SRS_COM.pdf Ref.3 AUTOSAR_SWS_COM.pdf 2. 为什么要使用Signal Group? 2.1 Traceabilty [RS_PO_00004] AUTOSAR shall define an open architecture for automotive software.…

debian和ubuntu的核心系统和系统命令的区别

Debian和Ubuntu虽然有很深的渊源,都是基于Debian的发行版,但它们在核心系统和系统命令上还是有一些差别的。以下是一些主要的不同之处: 1. 发布周期: - Debian: Debian项目采用滚动发布模型,持续更新&a…

【数据结构(邓俊辉)学习笔记】向量03——无序向量

文章目录 0.概述1.元素访问2.置乱器3.判等器与比较器4.无序查找4.1 判等器4.2 顺序查找4.3 实现4.4 复杂度 5. 插入5.1 算法实现5.2 复杂度分析 6. 删除6.1 区间删除6.2 单元删除6.3 复杂度 7. 唯一化7.1 实现7.2 正确性7.3 复杂度 8. 遍历8.1 实现8.2 复杂度 9. 总结 0.概述 …

vue3引入图片 无法使用require, vue3+vite构建项目使用require引入包出现问题需要用newURL来动态引入图片等静态资源

在vue3中 require引入图片的本地资源报错Uncaught (in promise) ReferenceError: require is not defined <template> <img :src"imageSrc" alt"My Image"> </template> <script> import imageSrc from /assets/image.png; export…

多媒体技术如何为地震体验馆增添更多真实元素?

近年来&#xff0c;为提升公众安全意识&#xff0c;众多体验式科普展馆纷纷崭露头角&#xff0c;其中地震体验馆尤为引人瞩目&#xff0c;成为学校安全教育的热门场景&#xff0c;接下来&#xff0c;我们就深入探索一下&#xff0c;这种运用了多媒体技术的地震体验馆&#xff0…

有哪些好用的电商API接口(京东|天猫|淘宝商品详情数据接口)

此API目前支持以下基本接口&#xff1a; 如何获取此API测试权限&#xff1f; item_get 获得淘宝商品详情item_get_pro 获得淘宝商品详情高级版item_review 获得淘宝商品评论item_fee 获得淘宝商品快递费用item_password 获得淘口令真实urlitem_list_updown 批量获得淘宝商品上…

云计算中的过度授权:安全隐患与应对策略

云计算凭借其弹性、可扩展等优势&#xff0c;已经成为诸多企业组织拓展业务的重要基础设施之一。然而&#xff0c;与传统IT架构相比&#xff0c;云计算环境的安全管理也面临着新的挑战。过度授权 (Overprivileging) 便是云安全领域亟待解决的主要问题之一&#xff0c;本文将带领…

开源模型应用落地-LangChain高阶-知识图谱助力记忆增强

一、前言 通过langchain框架调用本地模型&#xff0c;使得用户可以直接提出问题或发送指令&#xff0c;而无需担心具体的步骤或流程。langchain会自动将任务分解为多个子任务&#xff0c;并将它们传递给适合的语言模型进行处理。 本篇通过使用 ConversationKGMemory 组件&#…
最新文章