题目描述
思路解析动画文字版
记牢两步:先把父子边记成双向,再从 start 一层一层往外烧。最远那个节点是第几分钟烧到的,答案就是几。下面先建图,再点火。
关键洞察 · 感染能往父亲走：开火之前先想清楚一件事。普通的树,我们习惯只从父往子走;可感染是不管方向的,火能从孩子烧回父亲。所以要先把这棵树改造成一张无向图:每一条父子连线,都当成一条来回都能走的路。紫色标出的就是起点 3。下面一条边一条边地把这张图建起来。
建图 · 记双向边 1 和 5：把节点 1 和它的孩子 5 之间这条边记下来,而且是双向的:从 1 能走到 5,反过来从 5 也能走回 1。这样一来,原本只能父到子的关系,现在孩子也能烧回父亲了。
建图 · 记双向边 5 和 4：把节点 5 和它的孩子 4 之间这条边记下来,而且是双向的:从 5 能走到 4,反过来从 4 也能走回 5。两个红色节点就是这条边的两头。
建图 · 记双向边 4 和 9：把节点 4 和它的孩子 9 之间这条边记下来,而且是双向的:从 4 能走到 9,反过来从 9 也能走回 4。两个红色节点就是这条边的两头。
建图 · 记双向边 4 和 2：把节点 4 和它的孩子 2 之间这条边记下来,而且是双向的:从 4 能走到 2,反过来从 2 也能走回 4。两个红色节点就是这条边的两头。
建图 · 记双向边 1 和 3：把节点 1 和它的孩子 3 之间这条边记下来,而且是双向的:从 1 能走到 3,反过来从 3 也能走回 1。两个红色节点就是这条边的两头。
建图 · 记双向边 3 和 10：把节点 3 和它的孩子 10 之间这条边记下来,而且是双向的:从 3 能走到 10,反过来从 10 也能走回 3。两个红色节点就是这条边的两头。
建图 · 记双向边 3 和 6：把节点 3 和它的孩子 6 之间这条边记下来,而且是双向的:从 3 能走到 6,反过来从 6 也能走回 3。这是最后一条边,七条父子边全部记成了双向,无向图建好了。
第 0 分钟 · 起火：图建好了,回到起点。第 0 分钟,只有值为 3 的节点着火,把它标成焦点色。它到自己的距离是 0。接下来每过一分钟,火就从已经着火的节点向所有还没烧到的邻居蔓延一圈。
看起点 3 的邻居：在无向图里看看 3 的邻居有哪些:父亲 1,孩子 10,孩子 6,一共三个,都用红色圈出。注意父亲 1 也在里面,这正是普通往下搜索会漏掉的一支。这三个节点现在都紧挨着火源,下一分钟它们会一起被点燃。
第 1 分钟 · 点燃 1、10、6：第 1 分钟到,这几个红色候选一起被点燃: 1、10、6。它们和火源的距离都是 1,所以恰好在第 1 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
从 1 看邻居：轮到从节点 1 往外看。它的孩子 5 还没着火,标红当候选;孩子 3 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
从 10 看邻居：再看节点 10。它连着的只有 3,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
从 6 看邻居：再看节点 6。它连着的只有 3,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
第 2 分钟 · 点燃 5：第 2 分钟到,被点燃的是: 5。它们和火源的距离都是 2,所以恰好在第 2 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
从 5 看邻居：轮到从节点 5 往外看。它的孩子 4 还没着火,标红当候选;父亲 1 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
第 3 分钟 · 点燃 4：第 3 分钟到,被点燃的是: 4。它们和火源的距离都是 3,所以恰好在第 3 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
从 4 看邻居：轮到从节点 4 往外看。它的孩子 9、2 还没着火,标红当候选;父亲 5 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
第 4 分钟 · 点燃 9、2：第 4 分钟到,这几个红色候选一起被点燃: 9、2。它们和火源的距离都是 4,所以恰好在第 4 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
从 9 看邻居：再看节点 9。它连着的只有 4,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
从 2 看邻居：再看节点 2。它连着的只有 4,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
第 5 分钟 · 没有新节点：再往下试一分钟,看看最后点燃的 9、2 还能不能烧到新节点。它们都是叶子,连着的父亲早已着火,没有任何新目标。火到此彻底熄灭,不会再有第 5 分钟的战果。
回放 · 答案 = 4：把整场火回放一遍。第 0 分钟是 3,第 1 分钟 1、10、6,第 2 分钟 5,第 3 分钟 4,第 4 分钟 9 和 2。最远的 9 和 2 是第 4 分钟才烧到的,那就是全树感染完成的时刻。所以答案就是 start 到最远节点的距离,等于 4。
边界想清:单节点直接 0;从叶子出发要绕经父亲,距离更大;从根出发最远就是树高。
面试重点:核心是树转无向图求偏心距、DFS 与 BFS 两种等价写法、时间空间都是 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass Solution: def amountOfTime(self, root: Optional[TreeNode], start: int) -> int: def dfs(node: Optional[TreeNode], fa: Optional[TreeNode]): if node is None: return if fa: g[node.val].append(fa.val) g[fa.val].append(node.val) dfs(node.left, node) dfs(node.right, node) def dfs2(node: int, fa: int) -> int: ans = 0 for nxt in g[node]: if nxt != fa: ans = max(ans, 1 + dfs2(nxt, node)) return ans g = defaultdict(list) dfs(root, None) return dfs2(start, -1)复杂度
- 时间：O(n)，n 是节点数。建图一趟 DFS 走遍每个节点每条边;求距离再一趟 DFS,每个节点每条边也只访问常数次。两趟都是线性,合起来随节点数线性增长
- 空间：O(n)，按峰值算。邻接表存了每条边的两个方向,规模是 O(n);递归栈深度最坏在链状树时达到 O(n)。峰值就是 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心转化是什么?
追问DFS 和 BFS 两种写法有什么区别?
追问为什么时间和空间都是 O(n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
反转二叉树的奇数层
LeetCode 2415 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题