LC: 582. Kill Process
https://leetcode.com/problems/kill-process/
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:
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.lengthn == ppid.length1 <= n <= 5 * 1041 <= pid[i] <= 5 * 1040 <= ppid[i] <= 5 * 104Only one process has no parent.
All the values of
pidare unique.killis guaranteed to be inpid.
The Essence:
Die Eltern-Kind-Beziehung zwischen den Prozessen können wir als die Beziehungen zwischen den Knoten eines gerichteten Graphs betrachten. Wir müssen damit alle Knoten finden, die von dem Knoten mit dem Kill-Wert angefangen durchgelaufen werden können. Dieser Durchlauf muss effizient verarbeitet werden.
Details:
Der Graph kann durch etliche Datenstrukturen wie Arrays und Hashtabellen gebildet werden. Für die Traversierung stehen Tiefensuche und Breitensuche zur Verfügung.
Default Code:
Last updated