这道题目是通过递归遍历二叉树来计算从特定节点开始感染整棵树所需的时间。首先,需要构建一个辅助函数 traverse 来深度优先搜索(DFS)整棵树,并记录从起始感染节点传播到树的最远点所需的时间。在遍历过程中,我们需要确定每个节点作为感染源时感染其子树的最大深度。如果当前节点是感染起始节点,我们就记录从这个节点到其子树的最大深度;如果不是,我们则计算从当前节点到已感染节点的距离,并更新最大感染时间。这种方法确保了我们可以在单次遍历中计算出感染整棵树所需的时间。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
# 初始化最大距离
self.maxDistance = 0
# 开始遍历树
self.traverse(root, start)
# 返回最大距离,即感染所有节点所需的时间
return self.maxDistance
def traverse(self, root, start):
# 如果当前节点为空,返回0
if root is None:
return 0
# 递归计算左子树深度
leftDepth = self.traverse(root.left, start)
# 递归计算右子树深度
rightDepth = self.traverse(root.right, start)
# 如果当前节点是感染起始点
if root.val == start:
# 计算从起始点到最远子节点的最大距离
self.maxDistance = max(leftDepth, rightDepth)
# 返回一个特殊值表示这是起始点
return -1
elif leftDepth >= 0 and rightDepth >= 0:
# 如果当前节点不是起始点,更新深度
return max(leftDepth, rightDepth) + 1
else:
# 如果已到达感染节点,计算和更新可能的最大距离
distance = abs(leftDepth) + abs(rightDepth)
self.maxDistance = max(self.maxDistance, distance)
# 继续向上传递感染点信息
return min(leftDepth, rightDepth) - 1