题目：
给你一棵二叉树的根节点 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提交通过：
