2026-09-23：任务完成时间Ⅰ。用go语言，有 n 个任务，编号从 0 到 n-1，它们组成一棵以任务 0 为根的树。edges 中每个二元组表示前一个任务是后一个任务的直接上级。baseTime[i] 表示处理任务 i 本身需要的基础时长。
一个任务的最终完成时刻这样计算：如果它没有下级任务，那么它的完成时刻就等于 baseTime[i]。如果它有下级任务，就先从所有直接下级的完成时刻中找出最小值 earliest 和最大值 latest。用 latest 减 earliest，再加上这个任务自身的 baseTime[i]，得到该任务自身持续的时间。然后把这个自身持续时间加到 latest 上，得到该任务的完成时刻。
最后需要返回根任务 0 的完成时刻。
1 <= n <= 100000。
edges.length = n - 1。
edges[i] == [ui, vi]。
0 <= ui, vi <= n - 1。
ui != vi。
输入保证 edges 表示一棵有效的树。
baseTime.length == n。
1 <= baseTime[i] <= 100000。
每个任务的完成时间保证小于 2⁵³。
输入： n = 4, edges = [[0,1],[0,2],[2,3]], baseTime = [5,8,2,1]。
输出： 18。
解释：
任务 1 是叶子节点，因此其完成时间为 baseTime[1] = 8。
任务 3 是叶子节点，因此其完成时间为 baseTime[3] = 1。
任务 2 有一个子任务 3：
earliest = latest = 1
ownDuration = (latest - earliest) + baseTime[2] = 0 + 2 = 2
任务 2 的完成时间为 latest + ownDuration = 1 + 2 = 3
任务 0 有两个子任务，完成时间分别为 8 和 3：
earliest = 3, latest = 8
ownDuration = (latest - earliest) + baseTime[0] = (8 - 3) + 5 = 10
任务 0 的完成时间为 latest + ownDuration = 8 + 10 = 18
题目来自力扣3965。
一、建立"上级 → 下级"的邻接表
代码先创建一个长度为n的切片g，g[i]用来存放任务i的所有直接下级的编号。
然后遍历edges里每一条[x, y]：题目保证x是y的直接上级，所以直接把y追加进g[x]即可，不需要像无向图那样双向加边。
因为题目给定edges.length = n - 1，这一步总共追加n - 1次，最终g里恰好存了n - 1条父子关系。此时如果某个g[x]仍然是空的（nil），就说明任务x没有任何下级，也就是叶子。
二、从根节点 0 出发做后序遍历（DFS）
定义一个递归函数dfs(x)，它的语义非常明确：返回任务x的最终完成时刻。
之所以必须是"后序"（先子树、后自身），是因为一个任务的完成时刻完全由它所有下级的完成时刻决定——你不先把子树的结果算出来，当前节点就无从下手。而递归天然就是后序的：进入x后先把每个子节点递归到底，回到x时才做合并。
由于题目保证这是一棵以 0 为根的有效树，从 0 出发的 DFS 一定能不重不漏地覆盖全部n个节点，不需要 visited 数组，也不会有环。
三、叶子节点的处理
dfs(x)一进来先判断g[x] == nil。
• 如果成立，说明
x没有下级任务，按题目规则它的完成时刻就等于baseTime[x]，直接返回。• 这里有个顺带的好处：当
n = 1时，根节点 0 本身就是叶子，同样走这个分支返回baseTime[0]，不需要额外特判。
对于有下级的节点x，遍历g[x]里的每一个下级y，递归拿到t = dfs(y)，然后维护两个量：
•
earliest：所有t中的最小值，初始化为math.MaxInt（一个足够大的哨兵，保证第一个t一定能把它替换掉）。•
latest：所有t中的最大值，初始化为0。这里初值取 0 是安全的，因为baseTime[i] >= 1，任何任务的完成时刻都必然是正数，第一个t一定大于 0。
遍历完所有子节点后，earliest和latest就分别是"最快收尾的下级时刻"和"最慢收尾的下级时刻"。
五、合并公式（核心一步）
按题意，节点x自身的持续时间是：
ownDuration = (latest - earliest) + baseTime[x]而x的完成时刻是：
latest + ownDuration = latest + (latest - earliest) + baseTime[x]
= 2 × latest - earliest + baseTime[x]代码里直接写成了latest*2 - earliest + baseTime[x]，只是把上面的式子合并化简、省掉了中间变量，本质与题目描述完全一致。
可以这样直觉理解：所有下级任务是并行推进的，最慢的那个要到latest时刻才收尾；而x自身的处理需要占掉一段时长，这段时长由两部分构成——(latest - earliest)是等待各下级"对齐"所产生的空档期，baseTime[x]是自身的基础处理时长；并且这段自身处理被安排在latest之后串行执行，所以总完成时刻是latest + ownDuration。
关于数值安全：题目保证最终结果小于 2⁵³，而 Go 在 64 位平台上int本身就是 64 位，中间用int累加不会溢出，最后再转成int64返回。
六、返回根任务的结果
main里调用dfs(0)，得到的就是整棵树的最终完成时刻，转成int64后返回。
七、跟着样例走一遍
树形结构：0 → {1, 2}，2 → {3}，baseTime = [5, 8, 2, 1]。
情况
计算
返回
dfs(1)
叶子
直接取baseTime[1]
8dfs(3)
叶子
直接取baseTime[3]
1dfs(2)
只有下级 3
t = 1
，故earliest = latest = 1；1×2 − 1 + 2
3dfs(0)
下级 1 给 8，下级 2 给 3
earliest = 3
，latest = 8；8×2 − 3 + 5 = 16 − 3 + 5
18
最终输出18，与题目给的答案一致。
八、复杂度分析
总时间复杂度：O(n)
• 建邻接表：遍历
n - 1条边，每边一次追加，O(n)。• DFS：每个节点恰好进入一次（O(n) 次调用），每条父子关系恰好被遍历一次（O(n − 1) 次），每次操作都是常数时间。
• 两部分相加仍是 O(n)，且这是下界——你必须至少看完全部
n个节点和n − 1条边才能作答。
总额外空间复杂度：O(n)
（这里不计入输入edges和baseTime本身占用的空间。）
• 邻接表
g：n个切片头 +n − 1个存储的子节点编号，合计 O(n)。• 递归调用栈：深度等于树高。最坏情况是退化成一条链，深度达到
n，即 O(n)；最理想（树较平衡）时为 O(log n)。严格来说这部分的量级是O(树高)，其上界为 O(n)。• 没有 visited 数组、没有队列等其它辅助结构。
因此总体额外空间由邻接表和递归栈共同决定，上界为O(n)。
补充一点工程上的安心：n 最大到 10⁵，最坏递归深度也是 10⁵。Go 的 goroutine 栈会自动动态增长（上限很高），所以这种深度的递归不会像某些固定栈语言那样爆栈。Go完整代码如下：
package main
import (
"fmt"
"math"
)
func finishTime(n int, edges [][]int, baseTime []int)int64 {
g := make([][]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y) // 题目保证 x 是 y 的父节点
}
var dfs func(int)int
dfs = func(x int)int {
if g[x] == nil { // x 是叶子
return baseTime[x]
}
earliest, latest := math.MaxInt, 0
for _, y := range g[x] {
t := dfs(y)
earliest = min(earliest, t)
latest = max(latest, t)
}
return latest*2 - earliest + baseTime[x]
}
returnint64(dfs(0))
}func main() {
n := 4
edges := [][]int{{0, 1}, {0, 2}, {2, 3}}
baseTime := []int{5, 8, 2, 1}
result := finishTime(n, edges, baseTime)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import sys
from typing import List
def finishTime(n: int, edges: List[List[int]], baseTime: List[int]) -> int:
sys.setrecursionlimit(1000000)
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v) # u 是 v 的父节点
def dfs(x: int) -> int:
if not g[x]: # 叶子节点
return baseTime[x]
earliest = float('inf')
latest = 0
for y in g[x]:
t = dfs(y)
earliest = min(earliest, t)
latest = max(latest, t)
return latest * 2 - earliest + baseTime[x]
return dfs(0)
if __name__ == "__main__":
n = 4
edges = [[0, 1], [0, 2], [2, 3]]
baseTime = [5, 8, 2, 1]result = finishTime(n, edges, baseTime)
print(result)
C++完整代码如下：
using namespace std;long long finishTime(int n, vector int >>& edges, vector< int >& baseTime) {
vector int >> g(n);
for ( const auto& e : edges) {
int x = e[ 0 ], y = e[ 1 ];
g[x].push_back(y); // 题目保证 x 是 y 的父节点
}
function int )> dfs = [&]( int x) -> long long {
if (g[x].empty()) { // x 是叶子节点
return baseTime[x];
}
long long earliest = LLONG_MAX;
long long latest = 0 ;
for ( int y : g[x]) {
long long t = dfs(y);
earliest = min(earliest, t);
latest = max(latest, t);
}
return latest * 2 - earliest + baseTime[x];
};
return dfs( 0 );
}
int main() {
int n = 4 ;
vector int >> edges = {{ 0 , 1 }, { 0 , 2 }, { 2 , 3 }};
vector< int > baseTime = { 5 , 8 , 2 , 1 };
long long result = finishTime(n, edges, baseTime);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴