Re: [閒聊] 每日LeetCode
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：
---------------------------------------------------
class Solution {
public int amountOfTime(TreeNode root, int start) {
Map<Integer, List<Integer>> graph = new HashMap<>();
dfs(root, null, graph);
int res = -1;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
Set<Integer> visited = new HashSet<>();
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int id = queue.poll();
visited.add(id);
for (int next : graph.get(id)) {
if (!visited.contains(next)) {
queue.offer(next);
}
}
}
res++;
}
return res;
}
private void dfs(TreeNode root, TreeNode prev, Map<Integer,
List<Integer>> graph) {
if (root == null) return;
graph.put(root.val, new ArrayList<>());
if (prev != null) {
graph.get(root.val).add(prev.val);
}
if (root.left != null) {
dfs(root.left, root, graph);
graph.get(root.val).add(root.left.val);
}
if (root.right != null) {
dfs(root.right, root, graph);
graph.get(root.val).add(root.right.val);
}
}
}
---------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1704863434.A.7AE.html
推
01/10 13:34,
4月前
, 1F
01/10 13:34, 1F
推
01/10 16:52,
4月前
, 2F
01/10 16:52, 2F
討論串 (同標題文章)
完整討論串 (本文為第 598 之 719 篇)：
閒聊
1
3