题目描述
思路解析
一句话答案：LeetCode 1443 收集树上所有苹果的最少时间：把无向树建成邻接表，从 0 出发做后序 DFS，只有子树里真有苹果的边才往返计 2 秒，时间 O(n)。
从 0 出发收集所有苹果再回来，最少走几秒
给一棵 n 个节点的无向树，也就是节点间只有连接、不分父子方向，edges 每一项是一条连着两个节点的边。hasApple 标出哪些节点上挂着苹果。人从节点 0 出发，把所有苹果都摘到、再回到 0，每经过一条边花 1 秒，问最少总秒数。题面这棵树 n=7，边是 [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]，苹果在节点 2、4、5，答案是 8 秒。
为什么不能把整棵树老老实实走一圈
把每个节点都逛一遍再回来，是立刻能想到的走法。可节点 3、6 没苹果、下面也没挂别的，专门拐进去摘个空再退出来，纯属白走两趟。真正要回答的不是怎么走遍，而是哪些边非走不可。
一条边到底走不走，只问它下方有没有苹果
判断一条边要不要走，只看它靠叶子那端的子树里有没有苹果：但凡有一个苹果，这条边就非走不可，不跨过它就够不着那个苹果；一个苹果都没有，整支跳过。有个容易漏的点——判断子树含不含苹果，节点自己也得算进去：节点 2 的孩子都空着，可它本身有苹果，通往它的边照样得走。
一条必经的边为什么是 2 秒不是 1 秒：去摘苹果走一趟，摘完还得原路回出发点，一来一回两趟。而「子树里有没有苹果」，得先把孩子全部递归算完才知道，所以用后序，孩子那几支的秒数先递归到手，这条边才判得清。无向边先建邻接表，每条边的两个端点互相记成邻居；往下走时用一个 vis 数组记谁进过，遇到已进过的邻居直接跳过，就不会从孩子绕回父亲。
每个节点交回一支的秒数，根 0 收成总答案
递归到节点 u 时，先把它每个没进过的邻居都往下算一遍，孩子交回的秒数累加成一笔和。接着分两种：节点 u 自己没苹果、孩子那边也一秒都没带回来，这笔和是 0，说明整支没苹果，返回 0，通往 u 的边等于没走；只要不为 0，这支就有苹果，返回「进入 u 那条边的 2 秒加上这笔和」。根 0 是出发点、没有父边，边成本记 0，它最终交出来的就是整棵树的答案。
顺着题面这棵树，8 秒是怎么攒出来的
从叶子那头往回结算。节点 4 有苹果，边 1-4 记 2 秒；节点 5 有苹果，边 1-5 记 2 秒。回到节点 1，它没苹果，但孩子带回 4 秒，子树确有苹果，边 0-1 再添 2 秒，这支合计 6 秒交给根。
另一边，节点 3、6 都没苹果、也没有孩子，各返回 0；可回到节点 2，它自己有一个苹果，边 0-2 照记 2 秒，这支是 2 秒。根 0 合起来 6 加 2 得 8 秒，正是题面要的 8。若苹果只在 2、5，少了 4 那条边，算下来是 6 秒。
边算成 1 秒、忘了拦父亲，答案就废了
一条必经的边算成 1 秒，总数会少一半——它是往返两趟。无向边只往孩子方向建、或递归时不拦父节点，会在父子间无限递归爆栈，双向建边加 vis 挡一下才行。最隐蔽的是判断子树时漏掉节点自己，边就被错误跳过。
复杂度上，建邻接表把每条边记两遍是 O(n)，后序里每个节点靠 vis 只进一次、每条边只碰常数次，时间 O(n)；邻接表、vis 数组、最坏整棵树连成一条链时的递归栈都是 O(n)，空间 O(n)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢两句:通往一个节点的边,只有它子树里有苹果才走;每条要走的边来回算 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题