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

embedded/2024/12/23 4:10:41/

一、题目

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 = 0def dfs(rt: Optional[TreeNode]) -> int:if rt is None:return 0L = dfs(rt.left)R = dfs(rt.right)nonlocal retif rt.val == start:ret = max(ret, -min(L, R))return 1if L > 0 or R > 0:ret = max(ret, abs(L) + abs(R))return max(L, R) + 1return min(L, R) - 1dfs(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.ppmy.cn/embedded/19651.html

相关文章

max各种相机导出到ue4匹配镜头的工具集

总览 rollout export_UE4Cam_v2 "导出UE4Cam_v2:半自动" width:200 height:120(HyperLink explain "在打开的max文件中使用" pos:[25,12] width:200 height:15 color:(color 255 155 0) GroupBox grp1 "要导出的相机名" pos:[5,28] width:179 …

5367: 【图论】奇点数

题目描述 美术老师生病了,今天美术课编程老师来上,给大家一张无向图,包含 n个顶点(编号1∼n),m条边,求这张图中的奇点数。 偶点(even vertex):度数为偶数的顶点称为偶点 奇点(odd…

AI-数学-高中-44导数的运算法则

原作者视频:【导数】【一数辞典】3导数的运算法则(略难)_哔哩哔哩_bilibili 三种求导表达方式一样的,中间的比较常用: 链式法则:从外向内:

windows驱动开发-WDM框架(二)

DriverEntry 每个驱动程序必须具有 DriverEntry 例程,用于初始化驱动程序范围的数据结构和资源。 在支持即插即用 (PnP) 的驱动程序中,与所有驱动程序一样,DriverEntry 例程负责驱动程序初始化,而 AddDevice 例程负责设备初始化…

postman接口自动化

1.基础知识 1.打开postman新建一个文件夹。 (建立每一部分文件夹可以更好的管理接口信息) 2.postman基本介绍 这里用到的是我自己的一个项目。 params:查询字符串,一般作为url的一部分。 authorization :鉴权&…

attempt to compare nil with number -- 黑马点评出现问题

问题情况 : 主要问题 : 调用lua执行redis时,有一个值会接受nil(因为redis中没有该数据)或者数值,当该值为nil时执行报错,因为会用到将该值与其他数字比较,故报错attempt to compare nil with number 当然…

微信小程序:7.页面渲染

wx:if 在小程序中&#xff0c;使用wx&#xff1a;if“{{ condition }}”来判断是否需要渲染该代码块 <view wx:if"{{condation}}">你好帅</view>也可以用wx&#xff1a;if和wx&#xff1a;else来添加else判断&#xff1a; <view wx:if"{{type…

单片机通讯协议

参考&#xff1a;江科大单片机教程 STM32入门教程-2023版 细致讲解 中文字幕_哔哩哔哩_bilibili IIC通讯协议SPI通信协议UARTCANUSB速度100k-400khz4Mhz-线数2 CLK,DATA4CLK,ENB,IO,OI额外设备一主多从一主多从 一般不用自己写&#xff0c;都有相应的库或官方提供相应的&#…