LeetCode 582. 杀掉进程
题目描述
题意分析
两个等长列表按相同下标描述进程关系：
pid[i]是一个进程编号，ppid[i]是它的父进程编号。结束指定进程kill时，它的全部直接和间接子进程都会一同结束，返回这些进程编号，包含kill自身。进程关系是一棵树，结束某个进程只影响它的子树，不影响它的父进程或兄弟进程。编号是节点标识，不是数组下标；父编号零用于表示根没有真实父进程，不能把它当成需要结束的普通进程。
解法：构建树 + BFS
核心思路
[!blue]
原输入告诉每个进程“父亲是谁”，但要找全部后代，需要知道“孩子有哪些”。先把同下标的关系反过来登记，建立
graph[parent]到全部孩子编号的列表。同一个父进程可以对应多个孩子，不能只保存其中一个。随后从
kill做向下的 BFS。起点先入队，每弹出一个进程就把它加入结果，并将它的所有孩子加入队列。队列中保存的是已经确认受影响、尚未继续扩展后代的进程。从起点出发只能沿父到子的边移动，因此加入的节点一定是
kill或它的后代，不会越到祖先或兄弟分支。反过来，任何后代都有一条从kill向下到达它的路径，路径上的父节点被处理后就会把下一节点入队，所以不会漏掉间接后代。输入是无环的树，每个非根进程只有一个父进程，后代只会经由这一条路径被加入，不需要额外的访问集合。没有孩子的进程只加入结果，不再扩展；队列清空时，指定子树已经全部收集完毕。
Java 使用普通队列出队；Go 保留切片并用
head作为队头游标，循环条件每次读取最新长度，让后面追加的子进程也能继续被处理。这些差异不影响相同的 BFS 顺序。
解题步骤
- 按相同下标读取两个列表，将
pid[i]追加到graph[ppid[i]]。- 将
kill本身加入空队列。- 取出队头进程并加入结果，再把它的全部孩子入队。
- 重复直到没有待处理进程，返回收集到的编号。
代码实现
class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
// ppid 只给出「向上」的一条边，先反向建成 父 -> 子列表 才能向下扩散。
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < pid.size(); i++) {
graph.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
}
List<Integer> res = new ArrayList<>();
Deque<Integer> queue = new ArrayDeque<>();
// 起点本身也必须被收集，不只遍历它的孩子
queue.offer(kill);
while (!queue.isEmpty()) {
int cur = queue.poll();
res.add(cur);
List<Integer> children = graph.get(cur);
if (children == null) {
continue;
}
for (int next : children) {
queue.offer(next);
}
}
return res;
}
}
func killProcess(pid []int, ppid []int, kill int) []int {
// ppid 只给出「向上」的一条边，先反向建成 父 -> 子列表 才能向下扩散。
graph := make(map[int][]int)
for i := 0; i < len(pid); i++ {
graph[ppid[i]] = append(graph[ppid[i]], pid[i])
}
res := make([]int, 0)
// 用下标游标当队头，边遍历边追加，省掉真正的出队搬移。
// 起点本身也必须被收集，不只遍历它的孩子
queue := []int{
kill,
}
for head := 0; head < len(queue); head++ {
cur := queue[head]
res = append(res, cur)
for _, next := range graph[cur] {
queue = append(queue, next)
}
}
return res
}
复杂度分析
- 时间复杂度：期望 $O(n + k)$，
n为全部进程数，k为受影响进程数。建图扫描全部输入，遍历只处理指定子树；由于k <= n，总上界为 $O(n)$。- 空间复杂度：$O(n)$，父到子映射保存全部关系，队列与返回结果最多保存
k个进程。
关键点总结
[!green]
- 先把输入的父指针关系转成孩子列表，才能向下访问整棵子树。
- 起点自身先入队，每个出队节点都属于结果。
- 树的单父亲、无环性质保证不重复访问，Go 队列必须使用动态长度推进。
易错点总结
[!yellow]
- 将映射方向写成孩子到父亲，会向祖先扩展，无法得到需要结束的后代。
- 只从指定进程的孩子开始遍历，会漏掉
kill本身，叶子进程还可能得到空结果。- 一个父编号只保存一个孩子，会覆盖其他分支，遗漏整批后代。
- 把进程编号直接当作列表下标，无法处理不连续或顺序任意的编号。
- Go 用
range遍历初始队列长度，追加的后代不会自动成为新的遍历项；这里使用head < len(queue)。- 遇到一个没有孩子的进程就结束整个遍历，会漏掉队列中尚未处理的其他分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 690. 员工的重要性 | 中等 | 同样按父子关系访问全部后代，本题收集要结束的进程ID，原题累加员工重要度。 |
| 589. N 叉树的前序遍历 | 简单 | 进程父子关系可看成N叉树，遍历指定节点的整个子树即可得到所有受影响进程。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！