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

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>