Java Simple DFS & BFS Solution


  • 0
    F

    First introduce the DFS version. The idea is very simple, find the target employee, then add the important value and recursively call this function for its subordinates.
    If the employee id is not sorted, use a loop to find the target.

    class Solution {
        public int getImportance(List<Employee> employees, int id) {
            int sum = 0;
            for (Employee e: employees) {
                if (e.id == id) {
                    List<Integer> sub = e.subordinates;
                    sum += e.importance;
                    for (int i = 0; i < sub.size(); i++) {
                        sum += getImportance(employees, sub.get(i));
                    }
                    break;
                }
            }
            return sum;
        }
    }
    

    However, if the id is sorted, we can directly get the target employee.

    class Solution {
        public int getImportance(List<Employee> employees, int id) {
            int sum = 0;
            Employee e = employees.get(id - 1);
            if (e.id == id) {
                List<Integer> sub = e.subordinates;
                sum += e.importance;
                for (int i = 0; i < sub.size(); i++) {
                    sum += getImportance(employees, sub.get(i));
                }
            }
            return sum;
        }
    }
    

    The idea of BFS version is very similar.

    class Solution {
        public int getImportance(List<Employee> employees, int id) {
            int sum = 0;
            Employee e = employees.get(id - 1);
            Queue<Employee> queue = new LinkedList<>();
            queue.offer(e);
            while (!queue.isEmpty()) {
                e = queue.poll();
                sum += e.importance;
                List<Integer> sub = e.subordinates;
                for (int i = 0; i < sub.size(); i++) {
                    queue.offer(employees.get(sub.get(i) - 1));
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

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