题目描述
思路解析动画文字版
记牢两句:通往一个节点的边,只有它子树里有苹果才走;每条要走的边来回算 2 秒。后序就是先算孩子、再定自己这条边。下面每一帧都在套这条规则。
总览 · 树与苹果：先看清这棵树。紫色的节点 0 是出发点,也是最后要回到的地方。它的两个孩子是 1 和 2;节点 1 下面挂着 4 和 5,节点 2 下面挂着 3 和 6。苹果在节点 2、4、5。我们的目标是从 0 走出去,把这三个苹果都摘了,再回到 0,用的秒数越少越好。
建图 · 无向边变邻接表：题目给的是无向边,要先建邻接表:每条边两个方向都记一遍。然后把节点 0 当根,从它出发往下走,沿途遇到的节点就成了孩子。走的时候要用一个标记记住谁已经访问过,这样就不会从孩子又走回父亲、绕回去。方向定好了,这棵树就有了上下层级。
规则 · 哪条边值得走：动手前先把规则说死。第一,通往一个节点的边,要不要走,只看这个节点的子树里有没有苹果:有就必须走进去,没有就整支跳过。第二,凡是要走的边,都得算 2 秒,因为去摘苹果走一趟,摘完回出发点还要原路走回来,一条边来回两趟。带着这两条,开始后序搜索。
下行 · 进入根 0：后序深度优先搜索从根 0 开始。蓝色表示这个节点已经进入、正挂在搜索路径上,但它的结果还没定。根没有父亲,所以没有进入它的边,根本身不产生秒数。先往它的第一个孩子 1 走下去。
下行 · 进入节点 1：走到节点 1。它自己没有苹果,但现在还不能下结论,因为它下面还挂着 4 和 5,得先看孩子那边有没有苹果。继续往它的孩子里下探,先去 4。
下行 · 进入叶子 4：走到节点 4。它没有孩子,是个叶子,可以马上结算了。关键是:节点 4 上有苹果。子树里有苹果,那通往它的边就非走不可。
结算 · 边 1-4 计 2 秒：结算节点 4:它有苹果,所以通往它的边 1-4 必须走。绿色代表这个节点的子树要去、它的那条边要计入。边 1-4 来回 2 秒记下来,累计变成 2 秒。节点 4 把 2 秒这个结果交回给父亲 1。接着看 1 的另一个孩子 5。
下行 · 进入叶子 5：走到节点 5,它也是叶子,同样可以直接结算。节点 5 上也有苹果,和 4 一样,通往它的边躲不掉。
结算 · 边 1-5 计 2 秒：结算节点 5:有苹果,边 1-5 必须走,绿色标记,再加 2 秒,累计到 4 秒。现在节点 1 的两个孩子都看完了:4 带回 2 秒,5 带回 2 秒,合计 4 秒。回到节点 1,该决定它自己这条边了。
回溯 · 回到节点 1：回到节点 1。它自己没有苹果,但它的孩子 4 和 5 带回来 4 秒,说明它的子树里确实有苹果要收。子树里有苹果,通往节点 1 的那条边 0-1 也得走。
结算 · 边 0-1 计 2 秒：结算节点 1:虽然它自己没苹果,但子树里有,所以通往它的边 0-1 也要走,再加 2 秒。节点 1 变绿。它把自己这条边的 2 秒,加上孩子带回的 4 秒,一共 6 秒交还给根 0。累计到 6 秒。现在回根 0,去看它的另一个孩子 2。
下行 · 进入节点 2：从根 0 走到另一个孩子 2。节点 2 自己有苹果,但先别急着结算,它下面还挂着 3 和 6,按后序还是要先把孩子看完。先去 3。
下行 · 进入叶子 3：走到节点 3,叶子,可以直接结算。节点 3 上没有苹果,它又没有孩子,子树里空空如也。
结算 · 边 2-3 不走：结算节点 3:没有苹果,子树也没苹果,通往它的边 2-3 完全不用走。红色代表这条边跳过、贡献 0 秒。累计还是 6 秒不变。节点 3 把 0 交回给父亲 2。再看 2 的另一个孩子 6。
下行 · 进入叶子 6：走到节点 6,也是叶子。它上面同样没有苹果,子树里也没有别的节点。和 3 一个情况。
结算 · 边 2-6 不走：结算节点 6:没苹果,边 2-6 同样跳过,贡献 0 秒,标红。累计仍是 6 秒。现在节点 2 的两个孩子都看完了:3 带回 0,6 带回 0,孩子那边一个苹果都没有。回到节点 2 自己。
回溯 · 回到节点 2：回到节点 2。它的孩子 3、6 都没带回苹果,孩子方向是 0 秒。但别忘了一件事:节点 2 自己就有一个苹果!子树里有没有苹果,要把节点自己也算进去。所以子树 2 是有苹果的。
结算 · 边 0-2 计 2 秒：结算节点 2:因为它自己有苹果,通往它的边 0-2 必须走,加 2 秒。节点 2 变绿。它的两个孩子带回 0,所以子树 2 一共就是这 2 秒,交还给根 0。累计到 8 秒。注意这里的关键:哪怕孩子全没苹果,只要节点自己有,这条边照走。
结算 · 根 0,总计 8 秒：最后回到根 0。它的两支孩子:节点 1 那支带回 6 秒,节点 2 那支带回 2 秒,合起来 8 秒。根 0 是出发点,没有进入它的父边,所以它自己不再添秒数。整棵树搜完,答案就是 8 秒。
回放 · 4 条必经的边：回放一遍。真正走了的边只有 4 条:0-1、1-4、1-5、0-2,正好把节点 0 通向三个苹果 2、4、5 的路连起来。每条来回 2 秒,4 乘 2 等于 8。红色的 3 和 6 没苹果,通往它们的边 2-3、2-6 一步都没走,直接省掉。
对比 · 自己有苹果就要走：最后看一处最容易绕晕的地方。节点 2 的两个孩子 3、6 都没苹果,可通往 2 的边 0-2 照样走了,因为节点 2 自己有苹果。而通往 3、6 的边一条没走。这说明判断子树有没有苹果时,一定要把节点自己也数进去,不能只看孩子。
边界看三种:全无苹果或苹果只在出发点 0,答案都是 0;苹果在深处某叶子,答案就是从 0 到它那条路上的边数乘 2。
面试重点:后序是因为自己这条边的去留依赖孩子的结果;无向树靠邻接表加 vis 数组定根防回头;答案本质是必经边数乘 2,可递归也可两遍标记实现。
参考代码
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 Solution: def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: def dfs(u, cost): if vis[u]: return 0 vis[u] = True nxt_cost = 0 for v in g[u]: nxt_cost += dfs(v, 2) if not hasApple[u] and nxt_cost == 0: return 0 return cost + nxt_cost g = defaultdict(list) for u, v in edges: g[u].append(v) g[v].append(u) vis = [False] * n return dfs(0, 0)复杂度
- 时间：O(n)，建邻接表把每条边记两遍是 O(n)(树有 n-1 条边);后序 DFS 每个节点靠 vis 只访问一次,每条边只被遍历常数次。两步都是线性,总体 O(n)
- 空间：O(n)，邻接表存 2(n-1) 个邻居是 O(n),vis 数组 O(n),递归栈深度是树高 H、最坏退化成链时是 O(n)。三者按峰值取最大,空间 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么这道题要用后序遍历,先处理孩子再处理自己?
追问题目给的是无向树,你怎么定根、怎么防止递归走回头?
追问除了递归,还有别的理解或实现方式吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计二叉树中好节点的数目
LeetCode 1448 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题