2385.感染二叉树需要的总时间

链接：2385.感染二叉树需要的总时间
难度：Medium
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树
简介：返回感染整棵树需要的分钟数。

题解 1 - python

• 编辑时间：2024-04-24
• 执行用时：331ms
• 内存消耗：59.43MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        parent = {root:None}
        start_node = None
        q = deque([root])
        while q:
            node = q.popleft()
            if node.val == start: start_node = node
            if node.left: parent[node.left] = node; q.append(node.left)
            if node.right: parent[node.right] = node; q.append(node.right)
        def dfs(node: Optional[TreeNode], pre_node: Optional[TreeNode]):
            if not node: return 0
            res = 0
            if parent[node] and parent[node] != pre_node:
                res = max(res, dfs(parent[node], node))
            if node.left and node.left != pre_node:
                res = max(res, dfs(node.left, node))
            if node.right and node.right != pre_node:
                res=  max(res, dfs(node.right, node))
            return res + 1
        return dfs(start_node, None) - 1