專(zhuān)欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專(zhuān)欄：50多種經(jīng)典圖論算法全部掌握

最近在網(wǎng)上看到一個(gè)悲傷的事，一位24屆畢業(yè)生，在畢業(yè)當(dāng)天收到華為的終止入職通知，原因是體檢不合格，真的是畢業(yè)即失業(yè)。面試能通過(guò)說(shuō)明能力肯定是沒(méi)問(wèn)題的，體檢一般來(lái)說(shuō)如果不是特別嚴(yán)重的話，不會(huì)輕易終止的。

如果是入職體檢被拒一般來(lái)說(shuō)病情可能比較嚴(yán)重，因?yàn)槿肼汅w檢可查的項(xiàng)目不是很多，很多屬于個(gè)人隱私，是不能查的。入職體檢一般來(lái)說(shuō)費(fèi)用都不高，查的也不多，感覺(jué)就是走個(gè)形勢(shì)。真的是麻繩專(zhuān)挑細(xì)處斷，厄運(yùn)專(zhuān)找苦命人，只能默默祝福該網(wǎng)友早日康復(fù)。

--------------下面是今天的算法題--------------

來(lái)看下今天的算法題，這題是LeetCode的第1443題：收集樹(shù)上所有蘋(píng)果的最少時(shí)間，難度是中等。

給你一棵有 n 個(gè)節(jié)點(diǎn)的無(wú)向樹(shù)，節(jié)點(diǎn)編號(hào)為 0 到 n-1 ，它們中有一些節(jié)點(diǎn)有蘋(píng)果。通過(guò)樹(shù)上的一條邊，需要花費(fèi) 1 秒鐘。你從 節(jié)點(diǎn) 0 出發(fā)，請(qǐng)你返回最少需要多少秒，可以收集到所有蘋(píng)果，并回到節(jié)點(diǎn) 0 。

無(wú)向樹(shù)的邊由 edges 給出，其中 edges[i] = [fromi, toi] ，表示有一條邊連接 from 和 toi 。除此以外，還有一個(gè)布爾數(shù)組 hasApple ，其中 hasApple[i] = true 代表節(jié)點(diǎn) i 有一個(gè)蘋(píng)果，否則，節(jié)點(diǎn) i 沒(méi)有蘋(píng)果。

示例1：

輸入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] 輸出：8 解釋?zhuān)荷蠄D展示了給定的樹(shù)，其中紅色節(jié)點(diǎn)表示有蘋(píng)果。一個(gè)能收集到所有蘋(píng)果的最優(yōu)方案由綠色箭頭表示。

示例2：

輸入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] 輸出：6 解釋?zhuān)荷蠄D展示了給定的樹(shù)，其中紅色節(jié)點(diǎn)表示有蘋(píng)果。一個(gè)能收集到所有蘋(píng)果的最優(yōu)方案由綠色箭頭表示。

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 0 <= ai < bi <= n - 1

• hasApple.length == n

問(wèn)題分析

這題說(shuō)的是有 n 個(gè)節(jié)點(diǎn)的無(wú)向樹(shù)，沒(méi)說(shuō)是二叉樹(shù)，其實(shí)這個(gè)不影響，我們直接從根節(jié)點(diǎn) 0 開(kāi)始搜索，計(jì)算的時(shí)候采用自下往上的方式使用dfs計(jì)算花費(fèi)的時(shí)間。

如果子節(jié)點(diǎn)沒(méi)有蘋(píng)果，則到子節(jié)點(diǎn)不需要花費(fèi)時(shí)間，只需要判斷當(dāng)前節(jié)點(diǎn)有沒(méi)有蘋(píng)果即可，如果當(dāng)前節(jié)點(diǎn)有蘋(píng)果，我們就累加 2 ，因?yàn)榈疆?dāng)前節(jié)點(diǎn)一來(lái)一回需要花費(fèi) 2 秒時(shí)間。如果當(dāng)前節(jié)點(diǎn)沒(méi)有蘋(píng)果，也不需要到當(dāng)前節(jié)點(diǎn)，到當(dāng)前節(jié)點(diǎn)花費(fèi)的時(shí)間為 0 。

如果子節(jié)點(diǎn)有蘋(píng)果，無(wú)論當(dāng)前節(jié)點(diǎn)有沒(méi)有蘋(píng)果，都會(huì)經(jīng)過(guò)當(dāng)前節(jié)點(diǎn)，所以到當(dāng)前節(jié)點(diǎn)的時(shí)候，花費(fèi)的時(shí)間要累加 2 。

如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，無(wú)論根節(jié)點(diǎn)有沒(méi)有蘋(píng)果，都不需要花費(fèi)時(shí)間，因?yàn)槠鹗键c(diǎn)就是從根節(jié)點(diǎn)開(kāi)始的。

JAVA：

public int minTime(int n, int[][] edges, List hasApple)  {     List [] g =  new List[n];     for (int i = 0; i < n; i++)         g[i] = new ArrayList<>();     for (int[] edge : edges) {         g[edge[0]].add(edge[1]);         g[edge[1]].add(edge[0]);     }     return dfs(0, -1, g, hasApple); } private int dfs(int start, int parent, List [] g, List hasApple)  {     // 如果是葉子節(jié)點(diǎn)。     if (g[start].size() == 1 && g[start].get(0) == parent)         return hasApple.get(start) ? 2 : 0;     int total = 0;// 計(jì)算到子節(jié)點(diǎn)的蘋(píng)果中花費(fèi)的時(shí)間     for (int child : g[start]) {         if (child == parent)             continue;         total += dfs(child, start, g, hasApple);     }     if (parent == -1)// start是根節(jié)點(diǎn)。         return total;     elseif (total == 0) // start不是根節(jié)點(diǎn)，且子節(jié)點(diǎn)都沒(méi)有蘋(píng)果，返回當(dāng)前節(jié)點(diǎn)有沒(méi)有蘋(píng)果。         return hasApple.get(start) ? 2 : 0;     elsereturn total + 2;// 子節(jié)點(diǎn)有蘋(píng)果。 }

C++：

public:     int minTime(int n, vector

 > &edges, vector

 &hasApple) {         vector

 > g(n);         for (constauto &edge: edges) {             g[edge[0]].push_back(edge[1]);             g[edge[1]].push_back(edge[0]);         }         return dfs(0, -1, g, hasApple);     }     int dfs(int start, int parent, const vector

 > &g, const vector

 &hasApple) {         // 如果是葉子節(jié)點(diǎn)。         if (g[start].size() == 1 && g[start][0] == parent)             return hasApple[start] ? 2 : 0;         int total = 0; // 計(jì)算到子節(jié)點(diǎn)的蘋(píng)果中花費(fèi)的時(shí)間         for (int child: g[start]) {             if (child == parent)                 continue;             total += dfs(child, start, g, hasApple);         }         if (parent == -1) // start是根節(jié)點(diǎn)。             return total;         elseif (total == 0) // start不是根節(jié)點(diǎn)，且子節(jié)點(diǎn)都沒(méi)有蘋(píng)果，返回當(dāng)前節(jié)點(diǎn)有沒(méi)有蘋(píng)果。             return hasApple[start] ? 2 : 0;         elsereturn total + 2; // 子節(jié)點(diǎn)有蘋(píng)果。     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專(zhuān)注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫(xiě)算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。