Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2024-01-10 13:10:32
https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description
2385. Amount of Time for Binary Tree to Be Infected
给一个二元树和一个整数start,感染会从 start位置的节点往外扩散,每分钟往相邻
节点扩散一次,求出过几分钟后整个树都被感染。
Example 1:
https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png
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.
思路:
1.先利用dfs把二元树转成一个双向图。
2.再用bfs,从start位置开始,模拟感染的扩散,使用set避免往回走。
Java Code:
作者: JIWP (JIWP)   2024-01-10 13:34:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com