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