872. 终止进程

872. 终止进程

中文English

这个问题中. 每个进程都有一个唯一的 PID(进程id) 和 PPID(父进程id)。每个进程只有一个父进程，但可能有一个或多个子进程，这就像一个树形结构。并且只有一个进程的PPID是0，这意味着这个进程没有父进程。所有的pid都是不同的正整数。

我们使用两个整数列表来表示进程列表，其中第一个列表包含每个进程的PID，第二个列表包含对应的PPID。

现在给定这两个列表，以及一个你要终止(kill)的进程的ID，返回将在最后被终止的进程的PID列表。（当一个进程被终止时，它的所有子进程将被终止。返回的列表没有顺序要求）

样例

样例 1:

输入: PID = [1, 3, 10, 5], PPID = [3, 0, 5, 3], killID = 5
输出: [5, 10]
解释: 终止进程5同样会终止进程10.
     3
   /   
  1     5
       /
      10

样例 2:

输入: PID = [1, 2, 3], PPID = [0, 1, 1], killID = 2
输出: [2]

注意事项

1. 给定的kill id一定是PID列表中的某个id
2. 给定的PID列表中至少含有一个进程

class Solution:
    """
    @param pid: the process id
    @param ppid: the parent process id
    @param kill: a PID you want to kill
    @return: a list of PIDs of processes that will be killed in the end
    """
    ''' 
    大致思路:
    1.如果终止父进程，其对应的子进程也会被终止。可能存在一个父进程很多子进程的情况，所以需要给出一个方法，可以求得他的所有子进程
    2.while true，i计数，一直到i == len(res)的时候(放在调用找子进程方法下面判断)，此时可以break。最后返回res
    '''
    def __init__(self):
        self.res = []
    def killProcess(self, pid, ppid, kill):
        self.res.append(kill)
        return_res = []
        i = 0
        while self.res != []:
            #一直往res里面append
            kill = self.res.pop()
            return_res.append(kill)
            if kill in ppid:
                self.getSonProcess(pid, ppid, kill)
        return return_res

    def getSonProcess(self,pid,ppid,ppid_num):
        #去父进程列表里面进行查找ppid，可能存在多个相同的ppid(因为一个父进程存在多个字进程)
        dic_ppid = [index for index,value in enumerate(ppid) if value == ppid_num]
        for i in dic_ppid:
            self.res.append(pid[i])
        return self.res

 注:时间复杂度问题，lintcode未通过.