專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在網上看到一個悲傷的事，一位24屆畢業生，在畢業當天收到華為的終止入職通知，原因是體檢不合格，真的是畢業即失業。面試能通過說明能力肯定是沒問題的，體檢一般來說如果不是特別嚴重的話，不會輕易終止的。

如果是入職體檢被拒一般來說病情可能比較嚴重，因為入職體檢可查的項目不是很多，很多屬于個人隱私，是不能查的。入職體檢一般來說費用都不高，查的也不多，感覺就是走個形勢。真的是麻繩專挑細處斷，厄運專找苦命人，只能默默祝福該網友早日康復。

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

來看下今天的算法題，這題是LeetCode的第1443題：收集樹上所有蘋果的最少時間，難度是中等。

給你一棵有 n 個節點的無向樹，節點編號為 0 到 n-1 ，它們中有一些節點有蘋果。通過樹上的一條邊，需要花費 1 秒鐘。你從 節點 0 出發，請你返回最少需要多少秒，可以收集到所有蘋果，并回到節點 0 。

無向樹的邊由 edges 給出，其中 edges[i] = [fromi, toi] ，表示有一條邊連接 from 和 toi 。除此以外，還有一個布爾數組 hasApple ，其中 hasApple[i] = true 代表節點 i 有一個蘋果，否則，節點 i 沒有蘋果。

示例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 解釋：上圖展示了給定的樹，其中紅色節點表示有蘋果。一個能收集到所有蘋果的最優方案由綠色箭頭表示。

示例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 解釋：上圖展示了給定的樹，其中紅色節點表示有蘋果。一個能收集到所有蘋果的最優方案由綠色箭頭表示。

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

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

• hasApple.length == n

問題分析

這題說的是有 n 個節點的無向樹，沒說是二叉樹，其實這個不影響，我們直接從根節點 0 開始搜索，計算的時候采用自下往上的方式使用dfs計算花費的時間。

如果子節點沒有蘋果，則到子節點不需要花費時間，只需要判斷當前節點有沒有蘋果即可，如果當前節點有蘋果，我們就累加 2 ，因為到當前節點一來一回需要花費 2 秒時間。如果當前節點沒有蘋果，也不需要到當前節點，到當前節點花費的時間為 0 。

如果子節點有蘋果，無論當前節點有沒有蘋果，都會經過當前節點，所以到當前節點的時候，花費的時間要累加 2 。

如果當前節點是根節點，無論根節點有沒有蘋果，都不需要花費時間，因為起始點就是從根節點開始的。

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)  {     // 如果是葉子節點。     if (g[start].size() == 1 && g[start].get(0) == parent)         return hasApple.get(start) ? 2 : 0;     int total = 0;// 計算到子節點的蘋果中花費的時間     for (int child : g[start]) {         if (child == parent)             continue;         total += dfs(child, start, g, hasApple);     }     if (parent == -1)// start是根節點。         return total;     elseif (total == 0) // start不是根節點，且子節點都沒有蘋果，返回當前節點有沒有蘋果。         return hasApple.get(start) ? 2 : 0;     elsereturn total + 2;// 子節點有蘋果。 }

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) {         // 如果是葉子節點。         if (g[start].size() == 1 && g[start][0] == parent)             return hasApple[start] ? 2 : 0;         int total = 0; // 計算到子節點的蘋果中花費的時間         for (int child: g[start]) {             if (child == parent)                 continue;             total += dfs(child, start, g, hasApple);         }         if (parent == -1) // start是根節點。             return total;         elseif (total == 0) // start不是根節點，且子節點都沒有蘋果，返回當前節點有沒有蘋果。             return hasApple[start] ? 2 : 0;         elsereturn total + 2; // 子節點有蘋果。     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。