1443. Minimum Time to Collect All Apples in a Tree - Medium

前往題目

想法

• 建立一棵樹？
• 儲存每個node的鄰居？
• DFS?

思路

這題的關鍵在於

• 儲存每個node的鄰居
• 走訪全部節點

1. 儲存鄰居
2. DFS走訪所有節點
3. 不要走回父節點，不然會無限迴圈
4. 呼叫dfs往鄰居接著走訪
5. 當當前的節點是蘋果或是子節點有蘋果就代表來回需要兩秒，所以加上結果

Code

class Solution {
    List<List<Integer>> adj;
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        // Build adjacent edges
        adj = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            // build double connections
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        return dfs(0, -1, hasApple);
    }

    private int dfs(int cur, int parent, List<Boolean> hasApple) {
        int time = 0;

        for (int neighbor : adj.get(cur)) {
            // Prevent infinite loop
            if (neighbor == parent) continue;

            // Obtain its child time
            int childTime = dfs(neighbor, cur, hasApple);
            if (childTime > 0 || hasApple.get(neighbor)) {
                time += 2 + childTime;
            }
        }

        return time;
    }
}