Description#
You have n
processes forming a rooted tree structure. You are given two integer arrays pid
and ppid
, where pid[i]
is the ID of the ith
process and ppid[i]
is the ID of the ith
process's parent process.
Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0
, which means this process has no parent process (the root of the tree).
When a process is killed, all of its children processes will also be killed.
Given an integer kill
representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0582.Kill%20Process/images/ptree.jpg)
Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.
Example 2:
Input: pid = [1], ppid = [0], kill = 1
Output: [1]
Constraints:
n == pid.length
n == ppid.length
1 <= n <= 5 * 104
1 <= pid[i] <= 5 * 104
0 <= ppid[i] <= 5 * 104
- Only one process has no parent.
- All the values of
pid
are unique. kill
is guaranteed to be in pid
.
Solutions#
Solution 1: DFS#
We first construct a graph $g$ based on $pid$ and $ppid$, where $g[i]$ represents all child processes of process $i$. Then, starting from the process $kill$, we perform depth-first search to obtain all killed processes.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of processes.
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
def dfs(i: int):
ans.append(i)
for j in g[i]:
dfs(j)
g = defaultdict(list)
for i, p in zip(pid, ppid):
g[p].append(i)
ans = []
dfs(kill)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
private Map<Integer, List<Integer>> g = new HashMap<>();
private List<Integer> ans = new ArrayList<>();
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
int n = pid.size();
for (int i = 0; i < n; ++i) {
g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
}
dfs(kill);
return ans;
}
private void dfs(int i) {
ans.add(i);
for (int j : g.getOrDefault(i, Collections.emptyList())) {
dfs(j);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int, vector<int>> g;
int n = pid.size();
for (int i = 0; i < n; ++i) {
g[ppid[i]].push_back(pid[i]);
}
vector<int> ans;
function<void(int)> dfs = [&](int i) {
ans.push_back(i);
for (int j : g[i]) {
dfs(j);
}
};
dfs(kill);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func killProcess(pid []int, ppid []int, kill int) (ans []int) {
g := map[int][]int{}
for i, p := range ppid {
g[p] = append(g[p], pid[i])
}
var dfs func(int)
dfs = func(i int) {
ans = append(ans, i)
for _, j := range g[i] {
dfs(j)
}
}
dfs(kill)
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function killProcess(pid: number[], ppid: number[], kill: number): number[] {
const g: Map<number, number[]> = new Map();
for (let i = 0; i < pid.length; ++i) {
if (!g.has(ppid[i])) {
g.set(ppid[i], []);
}
g.get(ppid[i])?.push(pid[i]);
}
const ans: number[] = [];
const dfs = (i: number) => {
ans.push(i);
for (const j of g.get(i) ?? []) {
dfs(j);
}
};
dfs(kill);
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| use std::collections::HashMap;
impl Solution {
pub fn kill_process(pid: Vec<i32>, ppid: Vec<i32>, kill: i32) -> Vec<i32> {
let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
let mut ans: Vec<i32> = Vec::new();
let n = pid.len();
for i in 0..n {
g.entry(ppid[i]).or_insert(Vec::new()).push(pid[i]);
}
Self::dfs(&mut ans, &g, kill);
ans
}
fn dfs(ans: &mut Vec<i32>, g: &HashMap<i32, Vec<i32>>, i: i32) {
ans.push(i);
if let Some(children) = g.get(&i) {
for &j in children {
Self::dfs(ans, g, j);
}
}
}
}
|