690. 员工的重要性

2021-05-01 LeetCode 每日一题

链接：https://leetcode-cn.com/problems/employee-importance/

这里可以使用BFS/DFS去解题。因为我递归用的不怎么熟悉，所以选择用递推的方式。

因为题目提供的是员工的id，而我们需要计算员工的重要性，所以基本思路就是，先通过id拿到Employee，加入队列尾，每次循环，从队列头开始拿，直到队列为空，一次循环其实就相当于把某个员工的直接下属员工全部遍历了一遍。然后拿到该员工的直接下属员工，再加入队列尾。直到退出while循环即可。

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        int res = 0;
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(getEmployee(employees, id));

        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Employee employee = queue.poll();
                res += employee.importance;

                for (Integer childId : employee.subordinates) {
                    queue.offer(getEmployee(employees, childId));
                }
            }
        }

        return res;
    }

    private Employee getEmployee(List<Employee> employees, int id) {
        for (Employee e : employees) {
            if (e.id == id) {
               return e;
            }
        }

        return null;
    }
}

image.png