周赛2022.08.21—— 感染二叉树需要的总时间

2024年04月23日

luoyang

100

12 评论

leetcode

暂无标签

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

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

- 节点此前还没有感染。
- 节点与一个已感染节点相邻。
- 返回感染整棵树需要的分钟数。

### 输入输出
#### 示例1
![](https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png)
```
输入：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
![](https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png)
```
输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
```

**提示：**
- 树中节点的数目在范围 [1, 10^5] 内
- 1 <= Node.val <= 10^5
- 每个节点的值 互不相同
- 树中必定存在值为 start 的节点

### 解题思路
树的DFS + 图的BFS
#### DFS遍历树
首先需要通过对树的遍历，构建父亲到儿子，儿子到父亲的关系，这样就可以从上往下，从下往上对整个树进行遍历，从而实现感染的效果。
**注意**
父亲到儿子是1对2的关系，儿子到父亲是一对一的关系，注意这两种不同方向的存储。

### BFS遍历图
我们的目的就是从给定的节点start开始，对整个图完成BFS遍历，看看一共需要经历多少个step。
在遍历的过程中，我们每次从一部分节点感染，感染到相邻新的节点，下一步从这些新的节点开始感染即可。将所有感染的节点加入一个集合set中，当set数量等于整个图的数量的时候，这个时候就完成遍历操作了。

#### 代码实现
```
class Solution:
    def __init__(self):
        self.sums = 0

def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        father2son = defaultdict(list)
        son2father = dict()
        
        def order(root):
            if root is None:
                return
            self.sums += 1
            if root.left is not None:
                father2son[root.val].append(root.left)
                son2father[root.left.val] = root
                order(root.left)
            if root.right is not None:
                father2son[root.val].append(root.right)
                son2father[root.right.val] = root
                order(root.right)
        
        order(root)

infect_val = set([start])
        infect_new = set([start])
        times = 0
        while len(infect_val) < self.sums:
            infect_now = set()
            for node_val in infect_new:
                if node_val in father2son.keys():
                    node_li = father2son[node_val]
                    for node in node_li:
                        if node.val not in infect_val:
                            infect_val.add(node.val)
                            infect_now.add(node.val)

if node_val in son2father.keys():
                    node = son2father[node_val]
                    if node.val not in infect_val:
                        infect_val.add(node.val)
                        infect_now.add(node.val)
            infect_new = infect_now.copy()
            times += 1

return times
```

已有 12 条评论

jkncemhaoo 2024年10月01日 20:57
回复

看的我热血沸腾啊https://www.237fa.com/
afleioedvx 2024年11月26日 01:03
回复

《回档08之女王上位记》短片剧高清在线免费观看：https://www.jgz518.com/xingkong/17438.html
hpwjjjvivj 2025年02月28日 15:59
回复

文章紧扣主题，观点鲜明，展现出深刻的思考维度。
eilddddqrv 2025年03月04日 15:25
回复

每一个段落都紧密相连，逻辑清晰，展现了作者高超的写作技巧。
lswfinwhoh 2025年03月06日 23:49
回复

这篇文章不错！
kdtkpunlmb 2025年10月05日 01:22
回复

新盘新项目，不再等待，现在就是最佳上车机会！
posdpnhysk 2025年10月07日 10:08
回复

2025年10月新盘做第一批吃螃蟹的人coinsrore.com
新车新盘嘎嘎稳嘎嘎靠谱coinsrore.com
新车首发，新的一年，只带想赚米的人coinsrore.com
新盘上车集合留下我要发发立马进裙coinsrore.com
做了几十年的项目我总结了最好的一个盘（纯干货）coinsrore.com
新车上路，只带前10个人coinsrore.com
新盘首开新盘首开征召客户！！！coinsrore.com
新项目准备上线，寻找志同道合的合作伙伴coinsrore.com
新车即将上线真正的项目，期待你的参与coinsrore.com
新盘新项目，不再等待，现在就是最佳上车机会！coinsrore.com
新盘新盘这个月刚上新盘新车第一个吃螃蟹！coinsrore.com
ckkiyqfizp 2025年10月07日 10:08
回复

2025年10月新盘做第一批吃螃蟹的人coinsrore.com
新车新盘嘎嘎稳嘎嘎靠谱coinsrore.com
新车首发，新的一年，只带想赚米的人coinsrore.com
新盘上车集合留下我要发发立马进裙coinsrore.com
做了几十年的项目我总结了最好的一个盘（纯干货）coinsrore.com
新车上路，只带前10个人coinsrore.com
新盘首开新盘首开征召客户！！！coinsrore.com
新项目准备上线，寻找志同道合的合作伙伴coinsrore.com
新车即将上线真正的项目，期待你的参与coinsrore.com
新盘新项目，不再等待，现在就是最佳上车机会！coinsrore.com
新盘新盘这个月刚上新盘新车第一个吃螃蟹！coinsrore.com
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年10月31日 16:54
回复

华纳公司开户注册流程？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年11月01日 13:26
回复

华纳东方明珠客服邮箱？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年11月01日 15:16
回复

华纳东方明珠客服电话是多少？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠开户专线联系方式？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
如何联系华纳东方明珠客服？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠官方客服联系方式？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠客服热线？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠开户客服电话？（▲182（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠24小时客服电话？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠客服邮箱？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠官方客服在线咨询？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠客服微信？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年11月21日 14:31
回复

寻找华纳圣淘沙公司开户代理（183-8890-9465薇-STS5099】
华纳圣淘沙官方合作开户渠道（183-8890-9465薇-STS5099】
华纳圣淘沙公司开户代理服务（183-8890-9465薇-STS5099】
华纳圣淘沙公司开户咨询热线（183-8890-9465薇-STS5099】
联系客服了解华纳圣淘沙开户
（183-8890-9465薇-STS5099】
华纳圣淘沙公司开户专属顾问
（183-8890-9465薇-STS5099】