JAVA HashMap 3 solutions, BFS, DFS iterative&DFS recursive


  • 0
    //BFS solution
    public int getImportance(List<Employee> employees, int id) {
        int result = 0;
        HashMap<Integer, Employee> map = new HashMap<Integer, Employee>();
        for(Employee e: employees) map.put(e.id,e);
        Queue<Employee> BFS = new LinkedList<Employee>();
        BFS.offer(map.get(id));
        while(!BFS.isEmpty()){
            Employee current = BFS.poll();
            result+= current.importance;
            for(int sub_id: current.subordinates) BFS.offer(map.get(sub_id));
        }
        return result;
    }
    //DFS solution
    public int getImportance(List<Employee> employees, int id) {
        int result = 0;
        HashMap<Integer, Employee> map = new HashMap<Integer, Employee>();
        for(Employee e: employees) map.put(e.id,e);
        Stack<Employee> DFS = new Stack<Employee>();
        DFS.push(map.get(id));
        while(!DFS.isEmpty()){
            Employee current = DFS.pop();
            result+= current.importance;
            for(int sub_id: current.subordinates) DFS.push(map.get(sub_id));
        }
        return result;
    }
    //Recursive DFS
    public int getImportance(List<Employee> employees, int id) {
        HashMap<Integer, Employee> map = new HashMap<Integer, Employee>();
        for(Employee e: employees) map.put(e.id,e);
        return DFS(map, id);
    }
    public int DFS(HashMap<Integer, Employee> map, int id){
        Employee current = map.get(id);
        int result = current.importance;
        for(int sub_id: current.subordinates) result+= DFS(map, sub_id);
        return result;
    }

Log in to reply
 

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