Easy to understand Java DFS solution with comments


  • 0
    public class Solution {
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            
            //Make a map with parent and child processes
            Map<Integer, List<Integer>> gMap = new HashMap();
            for(int i = 0; i < ppid.size(); ++i) {
                if(gMap.containsKey(ppid.get(i))) {
                    gMap.get(ppid.get(i)).add(pid.get(i));
                }
                else {
                    List<Integer> list = new LinkedList();
                    list.add(pid.get(i));
                    gMap.put(ppid.get(i), list);
                }
            }
            
            List<Integer> retList = new ArrayList();  //Make a list to return 
            Set<Integer> check = new HashSet();  //Make a set to check if the process is already killed (Avoid duplicates and a possible infinite loop)
            
            makeList(retList, check, kill, gMap); //Call the DFS function
            
            return retList;
        }
        
        private void makeList(List<Integer> retList, Set<Integer> check, int kill, Map<Integer, List<Integer>> gMap) {
            if(check.contains(kill)) return;
            else {
                retList.add(kill);
                check.add(kill);
                if(gMap.containsKey(kill)) {
                    for(int i : gMap.get(kill)) {
                        makeList(retList, check, i, gMap);
                    }
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.