初学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

提交通过:

 

上一篇:Flutter应用下拉菜单设计DropdownButtonFormField控件介绍


下一篇:1、k8s问题pod从service中剔除