2385. 感染二叉树需要的总时间将-树转化为图+邻接表+广度优先遍历

2385. 2385. 感染二叉树需要的总时间将-树转化为图+邻接表+广度优先遍历

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

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

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

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

示例 1：

输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：

• 第 0 分钟：节点 3
• 第 1 分钟：节点 1、10、6
• 第 2 分钟：节点5
• 第 3 分钟：节点 4
• 第 4 分钟：节点 9 和 2
  感染整棵树需要 4 分钟，所以返回 4 。

示例 2：

输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。

我这题的做法时很有趣的，因为使用了图的很多内容，感兴趣的可以学习一下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int count;
  void node_num(struct TreeNode* root){
      if(root){
         node_num(root->left);
          node_num(root->right);
          count++;
      }
     
}
 

struct graph{
    int val;
    struct graph *next;
};

void add_graph(struct graph *G,int vex,int next){
    struct graph *node=(struct graph *)malloc(sizeof(struct graph));
    node->val=next;
    node->next=(G+vex)->next;
    (G+vex)->next=node;
}


void transform_tree_to_graph(struct graph *G,struct TreeNode* root){
   if(root){
       int vex=root->val;
       if(root->left){
           int next=root->left->val;
           add_graph(G,vex,next);
             add_graph(G,next,vex);
             transform_tree_to_graph(G,root->left);

       }
       if(root->right){
           int next=root->right->val;
           add_graph(G,vex,next);
             add_graph(G,next,vex);
              transform_tree_to_graph(G,root->right);

       }
   }
}


void print(struct graph *G){
     for(int i=0;i<count;i++){
         struct graph *p=(G+i)->next;
      
         while(p){
             printf("%d  ",p->val);
             p=p->next;
         }
        
    }

}


int amountOfTime(struct TreeNode* root, int start){
    count=0;
    node_num(root);
    int size=200000;
  
    struct graph *G=(struct graph *)malloc(sizeof(struct graph)*(size));
      int visit[size];
    for(int i=0;i<size;i++){
        (G+i)->next=NULL;
        visit[i]=1;
    }
    transform_tree_to_graph(G,root);
   // print(G);
  
    int Q[size];
    int rear=0,front=0;
    Q[rear++]=start;
    Q[rear++]=-1;
    int time=0;

    while(front!=rear){
        int de=Q[front++];
        if(de==-1){
            time++;
          
            if(rear!=front){
                 Q[rear++]=-1;
            }
            continue;

        }
       
         visit[de]=0;
        struct graph *p=(G+de)->next;
         while(p){
             if(visit[p->val]){
                 Q[rear++]=p->val;
                 visit[p->val]=0;

             }
             
           
             p=p->next;
         }
    }



 
    

  

        return time-1;

}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125