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

ops/2024/9/25 21:28:00/

一、题目

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/ops/14924.html

相关文章

解锁无限资源:用爬虫玩转石墨文档

石墨文档作为一款在线协作编辑工具,汇集了大量的优质文档资源。然而,有时我们需要更多、更广泛的资源,这时候,利用爬虫技术就能轻松获取到我们需要的文档。本文将详细介绍如何利用爬虫玩转石墨文档,解锁无限资源的奥秘…

第十五届蓝桥杯题解-好数

题目大意&#xff1a;一个数的低位为奇数&#xff0c;次低位为偶数&#xff0c;以此类推的数成为好数&#xff0c;例如&#xff1a;1&#xff0c;3&#xff0c;5&#xff0c;7&#xff0c;9 给定一个n&#xff0c;求1-n所有好数的个数&#xff0c;n<1e7 思路&#xff1a;一…

idm序列号永久激活码2023免费可用 IDM软件破解版下载 最新版Internet Download Manager 网络下载加速必备神器 IDM设置中文

IDM是一款多线程下载工具&#xff0c;全称Internet Download Manager。IDM的多线程加速功能&#xff0c;能够充分利用宽带&#xff0c;所以下载速度会比较快&#xff0c;而且它支持断点续传。它的网站音视频捕获、站点抓取、静默下载等功能&#xff0c;也特别实用。 idm使用技…

【网络安全】网络安全协议和防火墙

目录 1、网络层的安全协议&#xff1a;IPsec 协议族 &#xff08;1&#xff09;IP 安全数据报格式 &#xff08;2&#xff09;互联网密钥交换 IKE (Internet Key Exchange) 协议 2、运输层的安全协议&#xff1a;TLS 协议 3、系统安全&#xff1a;防火墙与入侵检测 1、网络…

WP-AutoPostPro 汉化版: WordPress自动采集发布插件 WordPress文章采集

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 WP-AutoPostPro 是目前最好用的WordPress自动采集发布插件&#xff0c;最大的特点是可以采集来自于任何网站的内容并自动发布到你的WordPress站点。真正做到可以采集任何网站的内容并…

服用5年份筑基丹 - Vue篇

前言 修仙之道&#xff0c;千回百转&#xff0c;每一步都充满了玄妙与机遇。在这条充满奇幻的修仙之路上&#xff0c;有一物至关重要&#xff0c;那便是筑基丹。此丹&#xff0c;凝聚了修仙者多年的心血与智慧&#xff0c;是修炼道路上的重要助力。 今日&#xff0c;我有幸得…

uni-app为图片添加自定义水印(升级版)

前置内容 uni-app为图片添加自定义水印&#xff08;解决生成图片不全问题&#xff09; UI 升级 现在水印样式变成这样了&#xff1a; 代码 <template><canvas v-if"waterMarkParams.display" canvas-id"waterMarkCanvas" :style"canv…

【XR806开发板试用】系统烧写

我是在虚拟机下安装&#xff0c;这部分大家应该都会吧&#xff0c;就不过多阐述了。 环境配置 大家应该先看官方文档【XR806】 1.准备工作 安装Git 在安装git后&#xff0c;需git-lfs并配置用户信息。否则可能拉代码失败 git config --global user.name “yourname” git co…