难度: Medium
Submission
运行时间: 59 ms
内存: 20.4 MB
class Solution:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
maps = {}
self.res = []
for i in range(len(ppid)):
parent = ppid[i]
son = pid[i]
if parent not in maps:
maps[parent] = []
maps[parent].append(son)
self.process(maps, kill)
return self.res
def process(self, maps, kill):
self.res.append(kill)
if kill in maps:
for next_node in maps[kill]:
self.process(maps, next_node)
Explain
这个题解采用了深度优先搜索（DFS）的方法来解决问题。首先，它建立了一个映射（maps），将每个父进程（ppid）映射到其子进程（pid）列表。然后，从要杀死的进程（kill）开始，使用递归函数process遍历整个进程树，将所有可达的子进程添加到结果列表（self.res）中。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
maps = {} # 存储父进程到子进程的映射
self.res = [] # 存储最终结果的列表
for i in range(len(ppid)):
parent = ppid[i]
son = pid[i]
if parent not in maps:
maps[parent] = []
maps[parent].append(son)
self.process(maps, kill)
return self.res
def process(self, maps, kill):
self.res.append(kill)
if kill in maps:
for next_node in maps[kill]:
self.process(maps, next_node) # 递归地遍历子进程
Explore
在构建映射时，通过遍历整个ppid列表，对每个父进程ID和对应的子进程ID进行映射。使用字典结构确保当多个子进程共享同一父进程时，这些子进程都会被添加到父进程的映射列表中。这种方法通过for循环和字典的键检查（`if parent not in maps`），确保不会遗漏任何子进程，并且每个子进程只被添加一次。这种数据结构的选择避免了重复添加同一个子进程。
递归函数`process`中确实有可能出现栈溢出的情况，特别是在进程树特别深或形成复杂结构时。为了预防栈溢出，可以考虑使用迭代的深度优先搜索（DFS）代替递归，使用显示的栈来管理待处理的节点。这种方法减少了函数调用栈的使用，从而降低栈溢出的风险。
如果`kill`指定的进程ID在pid列表中不存在，按照当前题解的逻辑，结果列表`self.res`将只包含`kill`ID本身，因为没有任何子进程关联到这个不存在的父进程ID。为了更准确地处理这种情况，可以在开始递归之前添加一个检查，确认`kill`ID是否真的存在于pid列表中。如果不存在，可以返回一个空列表或者适当的错误消息。
题解中使用了字典来映射父进程ID到子进程ID列表，这种方法自然支持非连续的进程ID。字典的键值对映射不依赖于进程ID的连续性，因此无论进程ID是否连续，都能正确地建立和查询父子进程关系。