FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/Python/kill-process.py at master · pythonpeixun/LeetCode-Solutions · GitHub

57 lines (49 loc) · 1.39 KB

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

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

# Time: O(n)

# Space: O(n)

import collections

# DFS solution.

class Solution(object):

def killProcess(self, pid, ppid, kill):

"""

:type pid: List[int]

:type ppid: List[int]

:type kill: int

:rtype: List[int]

"""

def killAll(pid, children, killed):

killed.append(pid)

for child in children[pid]:

killAll(child, children, killed)

result = []

children = collections.defaultdict(set)

for i in xrange(len(pid)):

children[ppid[i]].add(pid[i])

killAll(kill, children, result)

return result

# Time: O(n)

# Space: O(n)

# BFS solution.

class Solution2(object):

def killProcess(self, pid, ppid, kill):

"""

:type pid: List[int]

:type ppid: List[int]

:type kill: int

:rtype: List[int]

"""

def killAll(pid, children, killed):

killed.append(pid)

for child in children[pid]:

killAll(child, children, killed)

result = []

children = collections.defaultdict(set)

for i in xrange(len(pid)):

children[ppid[i]].add(pid[i])

q = collections.deque()

q.append(kill)

while q:

p = q.popleft()

result.append(p)

for child in children[p]:

q.append(child)

return result

Back | FazBrowse Home | New Git URL