2385. 感染二叉树需要的总时间将-树转化为图+邻接表+广度优先遍历
2023-09-14 09:06:49 时间
2385. 2385. 感染二叉树需要的总时间将-树转化为图+邻接表+广度优先遍历
给你一棵二叉树的根节点 root ,二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟,感染 将会从值为 start 的节点开始爆发。
每分钟,如果节点满足以下全部条件,就会被感染:
节点此前还没有感染。
节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
示例 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;
}
相关文章
- [LeetCode] Binary Tree Level Order Traversal 二叉树层次遍历(DFS | BFS)
- 二叉树的创建与遍历(链式存储)
- 从上往下打印二叉树
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 257 二叉树的所有路径
- Java实现 LeetCode 236 二叉树的最近公共祖先
- 【二叉树】LeetCode 94. 二叉树的中序遍历【简单】
- LeetCode(107): 二叉树的层次遍历 II
- 线索二叉树
- 一本正经的聊数据结构(5):二叉树的存储结构与遍历
- 重新整理数据结构与算法(c#)—— 二叉树排序树补删除节点[二十二]
- 【二叉树】LeetCode 543. 二叉树的直径【简单】
- 【二叉树】LeetCode 94. 二叉树的中序遍历【简单】
- 102. 二叉树的层序遍历
- 【7005】二叉树的遍历问题2
- 【b303】加分二叉树
- 翻转二叉树(C++)
- hdu 5444 Elven Postman(长春网路赛——平衡二叉树遍历)
- 层次遍历二叉树
- js 实现二叉树中序遍历
- 二叉树bst删除 删除叶子节点代码
- 【数据结构】红黑树与平衡二叉树的区别以及原理详解(附图解)