题目
解法1：
利用dfs，找出所有的在摘苹果的过程中会被访问的边。这些被访问的边数*2就是答案
这种做法需要保存当前路径，当发现当前路径包含苹果时，将这些边加入访问列表。这样做的坏处在于，每条边可能被加入多次，意味着时间复杂度的增加，事实证明这种做法确实不都快，刚刚过TLE的线。但利用字典或者set，还是可以不重复的记录摘苹果时需要被访问的边
class Solution:def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:# main idea: find the edges has been used through dfs, the total time is the number of used_edges*2# dfs to visited every nodedef dfs(node,path):# append current node to pathpath.append(node)visited[node] = True# if current node has apple, we add the edges in the path from root to current nodeif hasApple[node]:for i in range(1,len(path)):edge = (path[i-1],path[i])used_edge[edge] = Truefor nei in graph[node]:if not visited[nei]:dfs(nei,path[:])graph = collections.defaultdict(list)for i,edge in enumerate(edges):graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])# use a hashmap to store the used edges so that used edges won't be added repeatedly. set() can also worksused_edge = {
}visited = [False]*ndfs(0,[])return len(used_edge)*2
解法2
同样是利用dfs。不过这次直接返回两个变量，一个变量代表subtree里面有没有苹果，另一个代表subtree的访问时间，详见代码注释
class Solution:def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:# the dfs return two value:# 1. the first is a bool value, means if there is apples in the subtree of current node. If there is apple in the subtree, means that the time spent on the subtree needs to be counted# 2. the second value is the time spent on the subtree. According to the first value, we decide whether or not to add this timedef dfs(node):time = 0apple = hasApple[node]visited[node] = Truefor nei in graph[node]:if not visited[nei]:subapple,subtime = dfs(nei)apple = apple or subappleif subapple:time += subtime+2return apple,timegraph = collections.defaultdict(list)for i,edge in enumerate(edges):graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])visited = [False]*nreturn dfs(0)[1]
二刷
二刷的时候突然就有点想不太通，所有看到这种类型树的题目，都应该用一种bottom up的思想，不然就很容易陷入误区。重要的事情说三遍：bottom up,bottom up,bottom up!!!
c++版本解法2
class Solution {
public:pair<bool,int> helper(vector<vector<int>>& g,vector<int>& visited,vector<bool>& hasApple,int node){
visited[node] = 1;bool apple;if(hasApple[node]){
apple = true;}else{
apple = false;}int time = 0;for(auto& neigh : g[node]){
if(visited[neigh]) continue;pair<bool,int> sub = helper(g,visited,hasApple,neigh);apple = apple || sub.first;/*If the subnode itself has apple or any of its child has apple, we need to add the cost "2" to reach that sub node*/if(sub.first) time += sub.second+2;}return make_pair(apple,time);}int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
vector<vector<int>> g(n);for(auto& edge : edges){
g[edge[0]].push_back(edge[1]);g[edge[1]].push_back(edge[0]);}vector<int> visited(n,0);return helper(g,visited,hasApple,0).second;}
};
解法3
只使用一个返回变量，通过这个返回变量是否为0以及hasApple数组来判断是否需要增加cost。这边的关键在于理解这个2的递增到底代表什么，以及啥时候需要增加。详细见代码里面的注释
class Solution {
public:int helper(vector<vector<int>>& g,vector<int>& visited,vector<bool>& hasApple,int node){
visited[node] = 1;int res = 0;for(auto& neigh : g[node]){
if(visited[neigh]) continue;res += helper(g,visited,hasApple,neigh);}/*If 1. any of the child node has apple 2. the node it self has apple,we need to add the cost from the parrent node to the current node.note that this "2" here represents the cost from the parent node to the current node,that is why we need this && node!=0 here, because the node 0 does not have parent*/if((res > 0 || hasApple[node]) && node!= 0) res += 2;return res;}int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
vector<vector<int>> g(n);for(auto& edge : edges){
g[edge[0]].push_back(edge[1]);g[edge[1]].push_back(edge[0]);}vector<int> visited(n,0);return helper(g,visited,hasApple,0);}
};
时间复杂度：O(n),每个节点只需访问一遍
空间复杂度：O(n)