LeetCode 582. 杀掉进程

2022-05-26 HGNULB 约 9 分钟

文章信息 9 个分类 5 个标签

分类

题目描述

✅ 582. 杀掉进程

题意分析

给定两个等长数组 pid 与 ppid，ppid[i] 是进程 pid[i] 的父进程编号（根进程的父编号为 0，0 不是真实进程）。杀掉进程 kill 时，它的所有后代进程会被连带杀掉，要求返回被杀掉的全部进程编号，顺序任意。

题目明确说明所有进程构成一棵树，这句话透露了三条关键信息：每个进程至多有一个父进程，所以不存在两条路径通向同一个节点，遍历时不需要 visited 集合；树里没有环，所以遍历一定会终止；kill 的后代集合就是以 kill 为根的那棵子树的全部节点。

输入的方向是「反的」。ppid 描述的是每个节点指向父亲的边，而我们要做的事情是从 kill 出发向下找后代。沿着给定的边只能向上走，所以必须先把边反过来，建立父进程 -> 子进程列表的映射，才能一步步向下扩散。这个「反向建图」的动作是整道题的实质工作量，剩下的只是一次朴素遍历。

边界有两个。第一，kill 可能是一个叶子进程，它在映射里根本没有对应的子列表，取出来是 null 或空，必须允许这种情况而不是当成异常。第二，答案一定至少包含 kill 自己——哪怕它没有任何子进程，返回值也不能是空列表。

规模上进程数量可达 $5 \times 10^4$，编号取值范围很大且不连续，所以映射要用哈希表而不是按编号开数组。

解法：构建树 + BFS

核心思路

最直白的暴力法是：反复扫描 ppid，每轮把父进程已经在结果集里的进程也加进来，直到一轮下来结果集不再增长。这个做法正确，但每轮都要扫一遍长度为 $n$ 的数组，而链状结构下需要扫 $n$ 轮，最坏是 $O(n^2)$。瓶颈很明显：每次「找某个进程的孩子」都要全表扫描一次。

观察到这个查询会被重复执行很多次，而它的输入永远是「一个父进程编号」，输出永远是「它的子进程列表」，那就预先把它建成索引：一次 $O(n)$ 的遍历，把 pid[i] 塞进 graph[ppid[i]] 这个列表里。之后每次查孩子都是 $O(1)$ 均摊，暴力法的瓶颈直接消失。

建好 graph 后，问题变成标准的「从某个根出发收集整棵子树」。用队列做 BFS：队列里始终存放已经确定会被杀掉、但其子进程还没被展开的进程；结果列表里存放已经确定会被杀掉且已展开的进程。初始时队列只有 kill 一个元素，因为它是唯一已知会被杀的进程。

循环不变量是：结果列表与队列的并集，恰好是当前已经证明属于 kill 子树的全部节点，且队列中每个节点的子进程尚未加入这个并集。每一轮取出队首 cur，把它移入结果列表，同时把它的全部直接子进程入队——cur 的孩子必然也在 kill 的子树里，所以并集只增不错；cur 被展开后不再有未处理的孩子，不变量得以维持。

队列空时循环结束，说明再没有可展开的节点，结果列表就是完整的子树。因为题目保证是树，同一个进程只有一个父亲，只会被入队一次，所以既不用去重也不用 visited 数组。这里选 BFS 纯粹是实现简单；DFS 递归或显式栈得到的集合完全一样，只是输出顺序不同，而题目不要求顺序。

解题步骤

反向建图：遍历下标 i，执行 graph[ppid[i]].add(pid[i])。用 computeIfAbsent（Go 里直接 append 到 nil 切片）来处理某个父进程第一次出现的情况，避免手写「先判空再新建」。注意键是 ppid[i]、值里放 pid[i]，方向写反是最容易出的错。

初始化队列：队列里只放 kill。这一步同时保证了答案里一定包含 kill 自己——它会在第一轮被弹出并写入结果。

循环条件：队列不空。Java 版用 while (!queue.isEmpty())；Go 版用下标 head 当游标，head < len(queue) 表示还有未展开的元素，切片本身兼作结果缓冲，省掉出队时的元素搬移。

弹出并记账：取出队首 cur 后立刻 res.add(cur)。在出队时记账而不是入队时记账，两种写法都对，但要选定一种；同一个节点绝不会同时被两处写入，否则结果会重复。

展开子进程：取 graph.get(cur)。Java 的 HashMap.get 对不存在的键返回 null，必须先判空再遍历，否则叶子进程会直接抛空指针；Go 里读缺失键得到 nil 切片，range 一个 nil 切片是合法的零次循环，天然安全。把每个子进程入队。

返回结果列表，不需要排序。

以 pid = [1, 3, 10, 5]、ppid = [3, 0, 5, 3]、kill = 5 走一遍。

建图阶段逐条处理：i = 0 得 graph[3] = [1]；i = 1 得 graph[0] = [3]；i = 2 得 graph[5] = [10]；i = 3 把 5 追加到键 3 上，得 graph[3] = [1, 5]。最终映射为 {0: [3], 3: [1, 5], 5: [10]}，对应的树形结构是 3 为根，孩子是 1 和 5，而 5 的孩子是 10。

遍历阶段（每行给出「弹出的元素 → 结果列表 / 剩余队列」）：初始队列 [5]，结果 []。第一轮弹出 5，结果变为 [5]，查 graph[5] = [10]，10 入队，队列 [10]。第二轮弹出 10，结果变为 [5, 10]，查 graph[10] 不存在，跳过，队列空。循环退出，返回 [5, 10]。

注意进程 1 和 3 全程没有进入队列：3 是 5 的父亲，1 是 5 的兄弟，都不在 kill 的子树内。若建图时把方向写反成 graph[pid[i]].add(ppid[i])，则从 5 出发第一步就会走到父亲 3，再从 3 走到 0，最终返回 [5, 3, 0]——不但漏掉真正的后代 10，还把根本不该死的祖先和虚拟进程 0 杀掉了。

代码实现

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)$，其中 $n$ 是进程数量。建图遍历一遍全部下标，每次哈希插入均摊 $O(1)$；BFS 阶段每个进程至多入队一次、出队一次，所有子列表的长度之和恰好是边数 $n - 1$，因此展开操作的总次数也是线性的。

空间复杂度：$O(n)$，graph 中存储的元素总数等于进程数，队列在最坏情况下（某个进程有 $n - 1$ 个孩子）会同时容纳接近 $n$ 个元素，结果列表最多也是 $n$。这三部分都是线性的，无法再降——反向邻接表是这道题绕不开的开销。

关键点总结

输入给的是「孩子指向父亲」的边，而查询要「从父亲找孩子」，方向不匹配时的标准动作就是花 $O(n)$ 预处理反向邻接表，把 $O(n)$ 的查询降成 $O(1)$。这个「查询方向决定索引方向」的思路可迁移到几乎所有给定 parent 数组的树题。

题目说「构成一棵树」是一条可利用的约束，而不是背景描述：它直接省掉了 visited 集合和去重逻辑。面试时要主动说出「因为是树所以不需要判重」，这句话能证明你读懂了约束而不是套模板。

进程编号稀疏且范围大，映射必须用哈希表；只有编号连续且从 0 开始时才可以退化成数组邻接表。

BFS 与 DFS 在本题完全等价，因为要的是子树的集合而非层次或距离。面试官若追问选哪个，答案是「都可以，BFS 用显式队列避免了深链导致的递归栈溢出风险」——这才是有区分度的回答。

结果必须包含 kill 自身，把它作为队列初值是最自然的实现，比先写进结果再展开更不容易漏。

哈希表读不存在的键在 Java 与 Go 中行为不同（null 与 nil 切片），跨语言手写时这是必须记住的差异点。

易错点总结

建图方向写反：写成 graph[pid[i]].add(ppid[i])。pid = [1, 3, 10, 5]、ppid = [3, 0, 5, 3]、kill = 5 时会返回 [5, 3, 0]，杀掉了祖先和虚拟进程 0，真正的后代 10 反而活着。

Java 忘记判 graph.get(cur) == null：kill 是叶子进程时（如上例展开到 10），get 返回 null，紧接着的 for-each 直接抛 NullPointerException，整个用例崩溃而不是返回 [5, 10]。

结果里漏掉 kill 自己：把 kill 的孩子作为队列初值而不是 kill 本身。kill = 5 时返回 [10]，少了 5，任何叶子进程的用例都会直接返回空列表。

入队和出队都往结果里写一次：kill = 5 时 10 会被写入两次，返回 [5, 10, 10]，长度校验直接不通过。

用列表的 remove(0) 当出队：ArrayList.remove(0) 是 $O(n)$ 的元素搬移，进程数 $5 \times 10^4$ 且呈链状时整体退化到 $O(n^2)$，大数据用例超时。必须用 ArrayDeque 或下标游标。

按编号开数组当邻接表：进程编号可以取到很大的值且不连续，new List[n] 或 list[pid[i]] 会直接数组越界。

Go 里在 for range queue 的循环体内 append(queue, ...)：range 在循环开始时就已经取好了切片的长度快照，后追加的元素不会被遍历到，kill = 5 时只弹出 5 就结束，返回 [5]。必须用 for head := 0; head < len(queue); head++ 这种每轮重新求值的写法。

把这份代码原样搬去做一般图遍历：本题因为是树才敢省掉 visited；换成 ppid 允许重复（如 pid = [1, 2, 3]、ppid = [0, 1, 1] 再额外加一条 3 指向 2 的边）的有向图，节点 3 会被两条路径各入队一次，结果出现重复元素，若图中带环则队列永远不空、直接死循环。

把 ppid 里的 0 当成真实进程加入答案：0 只是根进程的占位父编号，它会作为键出现在 graph 中，但只要不从它出发就不会被访问；若额外遍历 graph 的所有键去凑答案就会把 0 带进来。

相似题目

题目	难度	考察点
1376. 通知所有员工所需的时间	中等	同样给 manager 父数组要反向建图，但收集的是根到叶路径上的耗时最大值而非节点集合
690. 员工的重要性	中等	子树求和而非收集编号，且邻接关系直接由 id 到下属列表给出，省去反向建图这一步
1110. 删点成林	中等	删的是节点本身而保留子树，需在递归返回时判断父指针是否置空并收集新根
863. 二叉树中所有距离为 K 的结点	中等	要向上也要向下走，必须先记录父指针把树当无向图，且此时必须加 visited
429. N 叉树的层序遍历	中等	同为多叉树 BFS，但要按层分组输出，循环里需先取当前层大小
207. 课程表	中等	一般有向图而非树，存在环，BFS 要配合入度数组做拓扑排序
133. 克隆图	中等	无向图遍历，存在多条路径通向同一节点，必须用哈希表兼做 visited 与新旧映射
310. 最小高度树	中等	同样是树上 BFS，但方向是自叶向内逐层剥离，考察度数的维护