LeetCode 690. 员工的重要性

约 4 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 哈希表 深度优先搜索 树 广度优先搜索

题目描述

✅ 690. 员工的重要性

image-20260929104548314

image-20260929104548484

image-20260929104548735

image-20260929104548927

题意分析

每名员工给出唯一编号、重要度和直属下属编号，需要求指定员工本人，以及他的所有直接、间接下属的重要度总和。

输入列表的顺序不代表上下级关系，编号也不等于列表下标。应先按编号建立索引，再从目标员工沿下属关系访问，避免遗漏深层下属或加入无关员工。

解法：哈希表 + DFS

核心思路

[!blue]

先建立 empMap[id] = employee，将下属列表里的编号转换为可以直接取得的员工对象。这样每次递归无需重新扫描整个员工列表。

定义 dfs(id) 返回编号为 id 的员工及其全部下属的重要度之和。先取出员工，把 total 初始化为他本人的重要度，再对每个直属下属递归调用 dfs，将返回的整棵下属子树贡献累加进来。

没有直属下属的员工无需继续递归，循环为空，直接返回自身重要度。对于有下属的员工，题目给定的上下级结构中，每名员工至多有一个直属上级，各直属下属分支不会重复包含同一个人；这些分支加上员工本人恰好覆盖所求范围。因此只要子调用返回正确的子树总和，当前调用的结果也正确。

遍历从指定员工开始，所以组织中其他分支不会进入求和。重要度允许为负，但题目要求完整累计这一层级的所有人，不能因为某个值为负就剪掉该分支。

解题步骤

  1. 遍历全部员工，以员工编号作为键建立映射。
  2. 从目标编号调用递归函数，查出对应员工对象。
  3. 先计入本人重要度，再递归累计每个直属下属的完整贡献。
  4. 返回当前总和，最外层的返回值就是目标员工及全部下属的重要度。

代码实现

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

    public int getImportance(List<Employee> employees, int id) {
        for (Employee emp : employees) {
            empMap.put(emp.id, emp);
        }

        return dfs690(id);
    }

    private int dfs690(int id) {
        Employee emp = empMap.get(id);
        // 先计入本人，再累加每名直属下属的完整子树贡献。
        int total = emp.importance;

        for (int subId : emp.subordinates) {
            total += dfs690(subId);
        }

        return total;
    }
}

func getImportance(employees []*Employee, id int) int {
    empMap := make(map[int]*Employee, len(employees))
    for _, emp := range employees {
        empMap[emp.Id] = emp
    }

    var dfs func(cur int) int
    dfs = func(cur int) int {
        emp := empMap[cur]
        // 先计入本人，再累加每名直属下属的完整子树贡献。
        total := emp.Importance
        for _, subId := range emp.Subordinates {
            total += dfs(subId)
        }
        return total
    }

    return dfs(id)
}

复杂度分析

设员工总数为 n，目标子树包含 m 名员工，高度为 h。

  • 时间复杂度：期望 $O(n+m)$。建立映射扫描全部员工，递归对目标范围内每个人访问一次；由于 m <= n，可以写为 $O(n)$。
  • 空间复杂度：Go 本次映射和递归栈为 $O(n+h)$。Java 的成员映射在同一实例中保留已有记录，若累计保存的不同编号数为 U，则为 $O(U+h)$；单次新实例调用时 U = n。

关键点总结

[!green]

  • 编号映射只负责快速查人，真正的遍历方向由直属下属列表决定。
  • 递归函数返回完整子树总和，父节点无需了解更深层的具体结构。
  • 本人与各直属下属分支构成所求人员范围，逐项累加即可。
  • 重要度的正负不影响是否访问，所有目标下属都必须计入。

易错点总结

[!yellow]

  • 把员工编号直接当列表下标，可能取错对象或越界。
  • 只累加直属下属的字段，遗漏更深层的间接下属。
  • 把全部员工都加入答案，会把目标层级以外的人也算进去。
  • 递归只累加下属而忘记当前员工，会漏掉本人贡献。
  • 发现负重要度就停止递归，会遗漏题目要求纳入的人员及其下属。

相似题目

题目 难度 关联与区别
582. 杀掉进程 中等 同样按ID到子节点列表遍历全部后代，原题收集进程ID，本题累加每个员工的重要度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/17376081
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！