2385.感染二叉树需要的总时间

发表于： 分类于：
字数： 1129 阅读：≈ 3分钟

☣ 2385.感染二叉树需要的总时间

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

  • 节点此前还没有感染。
  • 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数*。*

思路

基本思想

​ 因为被感染的节点都是当前节点的邻居节点，所以第一步就是要求出所有节点的邻居节点，又因为题目中说，所有的节点互不相同，所以可以用一个map存储所有节点的邻居节点

​ 节点的邻居节点无非就是父节点和两个孩子节点，所以可以直接用一次遍历，然后记录当前节点的父节点，遍历结束就可以形成所有节点的邻居节点，代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

//找到每一个节点的相邻节点
public void help(TreeNode root,TreeNode pre){
    if(root==null)
        return;
    List<Integer> neighbor=map.getOrDefault(root.val,new ArrayList<>());
    //将当前节点的邻居全部记录下来
    if(pre!=null)
        neighbor.add(pre.val);
    if(root.left!=null)
        neighbor.add(root.left.val);
    if(root.right!=null)
        neighbor.add(root.right.val);
    //将当前节点的所有邻居加入
    map.put(root.val,neighbor);
    set.add(root.val);
    help(root.left,root);
    help(root.right,root);        
}

​ 有了邻居节点之后，需要从一个start节点开始感染，每次感染的都是自己的邻居节点，相当于一层一层的扩散，这种层式的扩散可以使用层次遍历来模拟，每一层遍历的都是当前这一分钟被感染的节点，下一分钟将要被感染的节点就是当前这些节点的未被感染邻居节点

​ 为了判断哪些节点没有被感染，需要使用一个set来记录，正好在遍历的过程中就可以保存所有的节点，这样依赖就形成了完成的流程

执行流程

  1. 利用前序遍历求出所有节点的邻居节点，并且将所有的节点加入Set中
  2. 从start出发依次开始感染
  3. 被感染的节点从Set中删除，然后将当前被感染节点的未被感染邻居节点加入队列中
  4. 每次遍历一层结束之后，这一分钟分工作结束，分钟数+1
  5. 最后返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    //遍历一次统计每一个节点的相邻节点
    //然后从start出发，
    Map<Integer,List<Integer>> map;
    Set<Integer> set;
    public int amountOfTime(TreeNode root, int start) {
        //只有一个节点
        if(root.left==null&&root.right==null){
            return 0;
        }
        //保存所有节点的相邻节点
        map=new HashMap<>();
        //保存所有没被感染的节点
        set=new HashSet<>();
        help(root,null);
        //找到每一个节点的相邻节点之后，如何感染，如何判断感染完了
        //层序遍历
        Deque<Integer> queue=new LinkedList<>();
        queue.addLast(start);
        int res=-1;
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;++i){
                int node=queue.removeFirst();
                //被感染的节点剔除
                set.remove(node);
                //每一个节点都可以感染自己的邻居
                for(Integer neigh : map.get(node)){
                    //还没被感染的节点才加入队列
                    if(set.contains(neigh)){
                        queue.addLast(neigh);
                    }
                }
            }
            //当前一层节点被感染完
            ++res;
        }
        return res;
    }

    //找到每一个节点的相邻节点
    public void help(TreeNode root,TreeNode pre){
        if(root==null)
            return;
        List<Integer> neighbor=map.getOrDefault(root.val,new ArrayList<>());
        //将当前节点的邻居全部记录下来
        if(pre!=null)
            neighbor.add(pre.val);
        if(root.left!=null)
            neighbor.add(root.left.val);
        if(root.right!=null)
            neighbor.add(root.right.val);
        //将当前节点的所有邻居加入
        map.put(root.val,neighbor);
        set.add(root.val);
        help(root.left,root);
        help(root.right,root);        
    }
}

总结

主要是问题拆分，将感染问题拆分成两个子问题，先求出所有节点的邻居节点，然后根据题目，使用层次遍历模拟感染的过程，只有未被感染的节点才加入队列中，每感染一层，当前分钟的工作就完成了，对列为空时可以返回结果