题目描述
思路解析
一句话答案：LeetCode 2385 感染二叉树需要的总时间：感染能往父亲烧，先把树建成无向图，再从 start 做一遍 DFS 求到最远节点的距离就是答案，时间 O(n)、空间 O(n)。
感染要烧多少分钟
给一棵节点值互不相同的二叉树 root 和一个起点 start。第 0 分钟，值为 start 的节点着火；此后每过一分钟，凡是和已着火节点相邻、还没烧到的节点都会被点燃。问把整棵树烧完要几分钟。题面例子 root=[1,5,3,null,4,10,6,9,2]、start=3，答案是 4；只有一个节点时答案 0。
只往子节点搜，会漏掉什么
start=3 不是这棵树的根，它头顶还压着父亲 1，往上那一支还连着 5、4、9、2。要是照习惯只从 start 往子节点做 DFS、拿最大深度当答案，可火能从 3 烧回父亲 1 再拐下去，start 上方这半棵树整个够不着，分钟数会偏小。
为什么要把树改成无向图
火是不挑方向的：它能从父亲烧到孩子，也能从孩子烧回父亲。可二叉树的指针只有父指向子这一个方向，所以先把它改造成一张无向图——每一条父子连线都记成来回都能走的边。改完之后，每个节点旁边挂着它所有能烧到的邻居。这张图用邻接表存，也就是每个点记一份自己连到谁的名单。从 start 沿边烧，一个节点被点燃的时刻，恰好等于它到 start 隔的边数。
两趟 DFS：先建图，再量最远距离
第一趟 DFS 顺一条路走到底再回头，边走边建图：递归带上当前节点和它的父亲 fa，只要 fa 存在，就在 fa 和自己之间加上两条方向相反的邻接关系。孩子能烧回父亲，靠的就是这条反向边。
第二趟 DFS 从 start 出发量距离：对当前节点的每个邻居，只要它不是来路 fa，就递归下去，把「1 加上邻居那一支的返回值」取最大。返回的就是从这个节点起、沿图能烧到的最远距离。带 fa 这个参数是为了跳过来路，不然会沿刚走过的边折返，陷进死循环。start 那一趟返回的最大值，就是感染全树的总分钟数。
start=3 这棵树，逐分钟烧一遍
先把七条父子边都记成双向：1 和 5、5 和 4、4 和 9、4 和 2、1 和 3、3 和 10、3 和 6。现在从 3 点火，第 0 分钟只有 3。看 3 的邻居：父亲 1、孩子 10、孩子 6，它们离 3 都是一条边，第 1 分钟一起烧到。10 和 6 是叶子，连出去只剩烧过的 3。再看 1，它还连着 5，第 2 分钟烧到 5；5 又连着 4，第 3 分钟烧到 4；4 连着 9 和 2，第 4 分钟这两个一起烧到。9 和 2 是最后烧到的，离 3 隔了四条边，所以答案是 4。
两趟都是线性，坑全藏在方向和来路里
两趟 DFS 各把每个节点、每条边走一遍常数次，时间 O(n)；邻接表存了每条边的两个方向是 O(n)，链状树时递归栈最深到 O(n)，空间也是 O(n)，n 是节点数。
最容易栽的是忘了火能往上：只按父到子搜，start 上方整棵子树白白漏掉。建图时每条边要加两个方向，少加反向边，从 start 就走不回父亲。第二趟递归一定要带 fa 跳过来路，否则会沿刚走过的边折返、无限递归。还有别把答案当成节点总数或树高——它是 start 到最远节点隔的边数，单节点树这个距离就是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢两步:先把父子边记成双向,再从 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题