初学python记录：力扣2385. 感染二叉树需要的总时间

题目：

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

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

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

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

提示：

• 树中节点的数目在范围 [1, 105] 内
• 1 <= Node.val <= 105
• 每个节点的值 互不相同
• 树中必定存在值为 start 的节点

思考：

因为起始节点可能在二叉树的任何位置，所以将二叉树转换成无向图，记录每个节点的相邻节点，便于计算。

然后遍历图，计算起始节点到每个节点的距离，最大距离即为题目所求。代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import defaultdict
 
class Solution(object):
    def amountOfTime(self, root, start):
        """
        :type root: Optional[TreeNode]
        :type start: int
        :rtype: int
        """
        # 把二叉树转换成无向图
        # 字典的键表示每个节点的值，字典的值表示该节点相邻的节点的值
        # 为字典中尚未存在的键指定一个默认值（空列表）
        graph_dict = defaultdict(list)     
        
        def makeGraph(node, parent):
            if node:
                if parent:
                    graph_dict[node.val].append(parent.val)
                    graph_dict[parent.val].append(node.val)
                if node.left:
                    makeGraph(node.left, node)
                if node.right:
                    makeGraph(node.right, node)
 
        makeGraph(root, None)
 
        # 从起始节点开始找到最远的路径
        queue = [start]     # 队列
        visited = {start}    # 集合set储存已访问的节点
        distance = {start: 0}    # 字典表示每个节点距离起始点的距离
        ans = 0
        while queue:
            x = queue.pop(0)
            for node in graph_dict[x]:
                if node not in visited:
                    queue.append(node)
                    visited.add(node)
                    distance[node] = distance[x] + 1
                    if distance[node] > ans:
                        ans = distance[node]
        return ans

提交通过：