Last Updated on 2023-01-11 by Clay
題目
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.
Example 1:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] Output: 6 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 3:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] Output: 0
Constraints:
1 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai < bi <= n - 1fromi < toihasApple.length == n
題目會給定一個無向的樹結構，在特定的節點上會存在著蘋果（apple）。我們從原點 0 出發，要計算若要收集全部的蘋果，最少的秒數是多少。
每從一個節點走到另外一個節點，都是花一秒。最終我們還需要返回原點 0。
解題思路
深度優先搜索
由於題目給定的資料輸入是陣列，所以我會先建立一個 int -> array[int] 的 hash map，key 是節點，value 是節點所連接的其他節點編號組成的陣列。
另外，我也建立了一個 visited 的 hash map，用來記錄已經走過的節點，否則在走 DFS 時，怕會重新走回上一層的節點。
首先自然是把樹狀結構的連結關係用 hash map 儲存起來，接著用 DFS 走訪。每次走訪一個節點時，需要遍歷把連結的所有節點（除了上一層的節點）全部都再次丟入遞迴函式中；最後，如果底下的節點存在著蘋果、或是自身的節點就是蘋果，則在回傳時加上 2。
之所以加 2，是因為『走到這個節點』、『走回前一個節點』一定是 2 秒，對於每個節點都是。所以我們只要確認這個節點肯定必須走（底下有蘋果或是自身就有蘋果），就一定得加上 2 秒。
所以最後的答案，一定是『必須走的節點數 x 2』。
DFS 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
int DFS(int vertex, unordered_map<int, vector<int>>& trees, vector<bool>& hasApple, unordered_map<int, bool>& visited) {
// Init
int n = 0;
// We visit the current node, update the `visited`
visited[vertex] = true;
// DFS
for (auto& v: trees[vertex]) {
if (visited[v]) {
continue;
}
n += DFS(v, trees, hasApple, visited);
}
// If there are no any apple and the current node have no apple eigther, return 0
return n == 0 && !hasApple[vertex] ? 0 : n + 2;
}
int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
// Init
unordered_map<int, vector<int>> trees;
unordered_map<int, bool> visited;
for (auto& edge: edges) {
trees[edge[0]].emplace_back(edge[1]);
trees[edge[1]].emplace_back(edge[0]);
}
int num = DFS(0, trees, hasApple, visited);
return num ? num - 2 : 0;
}
};Python 範例程式碼
class Solution:
def DFS(self, vertex: int, trees: Dict[int, List[int]], hasApple: List[bool], visited: Dict[int, bool]) -> int:
# Init
n = 0
# We visit the current node, update the `visited`
visited[vertex] = True
# DFS
for v in trees[vertex]:
if (visited.get(v, False)):
continue
n += self.DFS(v, trees, hasApple, visited)
# If there are no any apple and the current node have no apple eigther, return 0
return 0 if n == 0 and not hasApple[vertex] else n + 2
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
# Init
trees = {}
visited = {}
for edge in edges:
trees[edge[0]] = trees.get(edge[0], []) + [edge[1]]
trees[edge[1]] = trees.get(edge[1], []) + [edge[0]]
num = self.DFS(0, trees, hasApple, visited)
return num - 2 if num else 0