2603. 收集树中金币 (opens new window)

1.广度优先搜索

解题关键在于想好哪个节点是一定要走的，如果过滤优化节点信息，同时合理利用树的性质。

优化一

叶子节点如果不包含硬币，那么这个叶子节点不需要到达。因此对于不含有硬币的叶子节点需要递归删除，直到所有叶子节点都是有硬币的。

优化二

叶子节点都包含硬币的条件下，因为收集距离为2，要想获取硬币不需要到达叶子节点。因此可以将所有叶子节点和父节点都删除。

经过上述操作和优化后，剩下的树每个叶子节点都需要到达，题目要求回到初始点，实际上相当于需要遍历整个树的所有节点，所以每个边都需要遍历走两次。假设剩下的树节点数量为n，那么遍历移动的边数为2*(n-1)。

算法思路

删除节点操作直接对每个节点的degree度数进行操作，度数小于等于0则说明已经被删除。

res统计上面两步优化后剩余树的所有节点，每次删除节点时res减一。

• 采用队列递归删除不含硬币的叶子节点，删除时需要同时更新叶子节点和相邻节点的度数。
• 删除两次叶子节点

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n=coins.length;
        List<Integer>[] g=new List[n];
        for(int i=0;i<n;i++){
            g[i]=new ArrayList<>();
        }
        int[] degree=new int[n];
        for(int i=0;i<edges.length;i++){
            int x=edges[i][0],y=edges[i][1];
            g[x].add(y);
            g[y].add(x);
            degree[x]++;
            degree[y]++;
        }
        Queue<Integer> queue=new LinkedList<>();
        int res=n;
        //递归删除没有硬币的叶子节点
        for(int i=0;i<n;i++){
            if(degree[i]==1&&coins[i]==0) queue.offer(i);
        }
        while(queue.size()>0){
            int node=queue.poll();
            degree[node]--;
            res--;
            for(Integer k:g[node]){
                degree[k]--;
                if(degree[k]==1&&coins[k]==0) queue.offer(k);
            }
        }
        //两次删除叶子节点
        for(int k=0;k<2;k++){
            for(int i=0;i<n;i++){
                if(degree[i]==1){
                    degree[i]--;
                    queue.offer(i);
                }
            }
            while(queue.size()>0){
                int node=queue.poll();
                degree[node]--;
                res--;
                for(Integer m:g[node]) degree[m]--;
            }
        }
        if(res==0) return 0;
        return 2*(res-1);
    }
}