LeetCode 690. 员工的重要性

Categories:

题目描述
思路分析
1. 解法一：哈希表 + DFS（推荐）
2. 解法二：哈希表 + BFS
相似题目

题目描述

✅ 690. 员工的重要性

思路分析

解法一：哈希表 + DFS（推荐）

核心思路：

先将所有员工信息存入哈希表，以 id 为键，快速查找员工

从目标员工出发，递归累加其重要性，再对每个下属递归求解

DFS 将整棵子树的重要性累加返回

复杂度分析：

时间复杂度：O(n)，其中 n 表示员工总数，每个员工最多访问一次

空间复杂度：O(n)，其中 n 为员工总数，用于哈希表和递归栈

class Solution {
    private Map<Integer, Employee> empMap = new HashMap<>();

    public int getImportance(List<Employee> employees, int id) {
        // 构建 id -> Employee 映射
        for (Employee emp : employees) {
            empMap.put(emp.id, emp);
        }

        return dfs(id);
    }

    private int dfs(int id) {
        Employee emp = empMap.get(id);
        int total = emp.importance;

        // 递归累加所有下属的重要性
        for (int subId : emp.subordinates) {
            total += dfs(subId);
        }

        return total;
    }
}

// Employee 定义
// type Employee struct {
//     Id           int
//     Importance   int
//     Subordinates []int
// }

func getImportance(employees []*Employee, id int) int {
    // 构建 id -> Employee 映射
    empMap := make(map[int]*Employee, len(employees))
    for _, emp := range employees {
        empMap[emp.Id] = emp
    }

    var dfs func(id int) int
    dfs = func(id int) int {
        emp := empMap[id]
        total := emp.Importance

        // 递归累加所有下属的重要性
        for _, subId := range emp.Subordinates {
            total += dfs(subId)
        }

        return total
    }

    return dfs(id)
}

解法二：哈希表 + BFS

核心思路：

同样先构建哈希表，然后用队列进行 BFS 层序遍历

每次出队一个员工，累加其重要性，并将其下属全部入队

遍历完整棵子树后返回总和

复杂度分析：

时间复杂度：O(n)，其中 n 表示员工总数

空间复杂度：O(n)，其中 n 为员工总数，用于哈希表和队列

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        // 构建 id -> Employee 映射
        Map<Integer, Employee> empMap = new HashMap<>();
        for (Employee emp : employees) {
            empMap.put(emp.id, emp);
        }

        int total = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);

        // BFS 遍历整棵子树
        while (!queue.isEmpty()) {
            Employee emp = empMap.get(queue.poll());
            total += emp.importance;

            for (int subId : emp.subordinates) {
                queue.offer(subId);
            }
        }

        return total;
    }
}

func getImportance(employees []*Employee, id int) int {
    // 构建 id -> Employee 映射
    empMap := make(map[int]*Employee, len(employees))
    for _, emp := range employees {
        empMap[emp.Id] = emp
    }

    total := 0
    queue := []int{id}

    // BFS 遍历整棵子树
    for len(queue) > 0 {
        emp := empMap[queue[0]]
        queue = queue[1:]
        total += emp.Importance

        for _, subId := range emp.Subordinates {
            queue = append(queue, subId)
        }
    }

    return total
}

相似题目

题目	难度	考察点
133. 克隆图	中等	DFS、BFS、哈希表
547. 省份数量	中等	DFS、并查集
200. 岛屿数量	中等	DFS、BFS
1376. 通知所有员工所需的时间	中等	DFS、树
104. 二叉树的最大深度	简单	DFS、BFS
559. N 叉树的最大深度	简单	DFS、BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/17376081