力扣690题：员工重要度解决方案

一、问题理解

题目要求我们计算一个员工及其所有下属(包括下属的下属)的重要度总和。这是一个典型的树形结构遍历问题，可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。

二、数据结构分析

每个员工对象包含三个属性：

1. id: 唯一标识符

2. importance: 该员工的重要度值

3. subordinates: 直接下属的ID列表

三、解决思路

1. ‌哈希表预处理‌：首先将所有员工信息存入哈希表，以id为键，这样可以在O(1)时间内找到任意员工。

2. ‌广度优先搜索(BFS)‌：

• 累加其重要度

• 将其所有下属加入队列

• 从给定的员工id开始

• 将其加入队列

• 循环处理队列中的每个员工：

• 直到队列为空，返回累计的重要度

四、完整代码

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        // 创建哈希表快速查找员工
        unordered_map<int, Employee*> emp_map;
        for (auto emp : employees) {
            emp_map[emp->id] = emp;
        }
       
        // 使用队列进行广度优先搜索(BFS)
        queue<int> q;
        q.push(id);
        int total_importance = 0;
       
        while (!q.empty()) {
            int current_id = q.front();
            q.pop();
           
            // 获取当前员工对象
            Employee* current_emp = emp_map[current_id];
            // 累加重要度
            total_importance += current_emp->importance;
           
            // 将下属加入队列
            for (int sub_id : current_emp->subordinates) {
                q.push(sub_id);
            }
        }
       
        return total_importance;
    }
};

五、代码详解

1. ‌哈希表构建‌：unordered_map<int, Employee*> emp_map存储所有员工信息

2. ‌队列初始化‌：queue<int> q用于BFS遍历

3. ‌BFS循环‌：

• q.front()获取当前处理的员工id

• emp_map[current_id]获取员工对象

• total_importance += current_emp->importance累加重要度

• 将下属id加入队列继续处理

4. ‌返回结果‌：当队列为空时，total_importance即为所求

六、示例分析

假设输入：
employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]]
id = 1

执行过程：

1. 处理id=1，重要度+5，下属2,3入队

2. 处理id=2，重要度+3，无下属

3. 处理id=3，重要度+3，无下属

4. 队列空，返回5+3+3=11