amount-of-time-for-binary-tree-to-be-infected

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Convert the tree to an undirected graph to make it easier to handle.

Use BFS starting at the start node to find the distance between each node and the start node. The answer is the maximum distance.

Algorithms

You are given the <code>root</code> of a binary tree with unique values, and an integer <code>start</code>. At minute <code>0</code>, an infection starts from the node with value <code>start</code>.

Each minute, a node becomes infected if:

<ul>
	<li>The node is currently uninfected.</li>
	<li>The node is adjacent to an infected node.</li>
</ul>

Return the number of minutes needed for the entire tree to be infected.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png" style="width: 400px; height: 306px;" />
<pre>
Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png" style="width: 75px; height: 66px;" />
<pre>
Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 105]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 105</code></li>
	<li>Each node has a unique value.</li>
	<li>A node with a value of <code>start</code> exists in the tree.</li>
</ul>

第 307 场周赛

weekly-contest-307

amountOfTime

资深工程师

Amount of Time for Binary Tree to Be Infected

Maximum Depth of Binary Tree

maximum-depth-of-binary-tree

二叉树的最大深度

Shortest Path to Get Food

shortest-path-to-get-food

获取食物的最短路径

All Nodes Distance K in Binary Tree

all-nodes-distance-k-in-binary-tree

二叉树中所有距离为 K 的结点

Count the Number of Infection Sequences

count-the-number-of-infection-sequences

统计感冒序列的数目

Tree

Depth-First Search

Breadth-First Search

Hash Table

Binary Tree

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

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

<ul>
	<li>节点此前还没有感染。</li>
	<li>节点与一个已感染节点相邻。</li>
</ul>

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

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png" style="width: 400px; height: 306px;">
<pre>输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2
感染整棵树需要 4 分钟，所以返回 4 。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png" style="width: 75px; height: 66px;">
<pre>输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点的数目在范围 <code>[1, 105]</code> 内</li>
	<li><code>1 &lt;= Node.val &lt;= 105</code></li>
	<li>每个节点的值 互不相同</li>
	<li>树中必定存在值为 <code>start</code> 的节点</li>
</ul>

感染二叉树需要的总时间

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

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

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

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

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

 

示例 1：

[https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png]

输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2
感染整棵树需要 4 分钟，所以返回 4 。


示例 2：

[https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png]

输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。


 

提示：

 * 树中节点的数目在范围 [1, 105] 内
 * 1 <= Node.val <= 105
 * 每个节点的值 互不相同
 * 树中必定存在值为 start 的节点