LeetCode 690. 员工的重要性

2022-10-20 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 690. 员工的重要性

题意分析

要什么：给一组员工记录，每条记录包含员工 id、重要度、以及直接下属的 id 列表。给定一个 id，返回这名员工加上他所有层级下属的重要度总和。
约束透露的信号：下属关系是单向的、逐层向下的，整个结构就是一棵（或若干棵）以 id 为节点的树——所以「所有层级下属」等价于「整棵子树」，求和就是一次子树遍历。真正的技术障碍在于输入给的是一个扁平列表，而下属只用 id 引用：拿到一个下属 id 无法直接得到它的记录，只能线性去列表里找。这就要求先把 id 到记录的映射建出来，否则每次查下属都是 $O(n)$，整体退化成 $O(n^2)$。
边界：目标 id 保证存在于列表中；叶子员工的下属列表为空，此时贡献就是自身重要度；重要度可以为负；员工 id 不一定连续、也不一定从 1 开始，所以只能用哈希表而不能用数组下标直接映射；题目保证不存在环（否则递归不会终止）。

解法：哈希表 + DFS

核心思路

朴素做法是：从目标员工出发，每要展开一个下属就在员工列表里线性查找对应记录。逻辑是对的，但每次查找 $O(n)$、总共要查 $O(n)$ 次，整体 $O(n^2)$。
瓶颈非常明确：同一份列表被反复线性扫描，只为了做「按 id 取记录」这一件事。这正是哈希表存在的意义——把一次 $O(n)$ 的查找换成 $O(1)$。
于是解法分成两步。第一步预处理：遍历一遍员工列表，建立 id -> Employee 的哈希表。第二步遍历：从目标 id 开始做深度优先搜索。
递归函数的契约（不变量）是：dfs(id) 返回以 id 为根的整棵子树的重要度之和，即该员工自身的重要度加上所有直接下属各自子树的和。这个定义是自洽的递归——叶子节点没有下属，返回值就是自身重要度，构成天然的递归出口，不需要额外写终止判断。
为什么不需要 visited 标记？因为结构是树（或森林），每个节点只有一个父亲，从目标出发向下走不会重复到达同一个节点，也不会成环。这是树形 DFS 与图形 DFS 的关键差别，也是这题在面试里常被追问的点。

解题步骤

先遍历员工列表，把每条记录按 id 存进哈希表。为什么必须先建表再递归：递归展开下属时随时要按 id 取记录，如果边建表边递归，可能遇到尚未入表的下属；一次性建好可以彻底消除顺序依赖。为什么用哈希表而不是数组：id 的取值范围可能很大且不连续，用数组要么浪费大量空间，要么根本装不下。

定义递归函数：取出当前 id 的记录，先把自身重要度计入 total。为什么先算自己：契约规定返回值包含自身，先加上去可以让后续只关心下属，逻辑不会漏项也不会重复。

遍历该记录的下属 id 列表，对每个下属递归调用并把返回值累加进 total。为什么可以直接相加：不同下属的子树互不相交（树结构保证一个员工只有一个上级），所以子树和之间不会重复计数。

返回 total。为什么没有显式的递归出口：下属列表为空时 for 循环一次都不执行，函数直接返回自身重要度，出口已经隐含在循环里了。

主函数返回 dfs(目标 id)。

以 employees = [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]]、id = 1 走一遍。先建表得到 {1: 记录1, 2: 记录2, 3: 记录3}。调用 dfs(1)：取出记录 1，total = 5；它有两个下属。先递归 dfs(2)：取出记录 2，total = 3，下属列表为空，循环不执行，返回 3；主调用把 total 累加成 8。再递归 dfs(3)：同理返回 3；total 累加成 11。记录 1 的下属遍历完毕，返回 11。整个过程只访问了三个节点，每次取记录都是哈希表的 $O(1)$ 命中，没有任何线性查找。若把 id 换成 2，则只会访问记录 2，返回 3——这印证了契约里的「以该员工为根的子树」，上级的重要度不会被计入。

代码实现

// 核心实现：哈希表 + DFS，维护必要状态并避免重复处理。
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;
    }
}

// 核心实现：哈希表 + DFS，维护必要状态并避免重复处理。

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)
}

复杂度分析

时间复杂度：$O(n)$，n 为员工总数。凭什么：建表遍历一遍列表；DFS 阶段每个节点最多被访问一次（树结构无环无重复路径），每次访问做一次 $O(1)$ 的哈希查找和常数次加法；所有下属列表的长度之和不超过 n。

空间复杂度：$O(n)$。凭什么：哈希表保存全部 n 条记录；递归栈的深度等于树高，最坏情况下（一条链式的汇报关系）为 $O(n)$。

关键点总结

「用 id 互相引用的扁平列表」= 先建索引再遍历。这是把「逻辑上的图 / 树」从「物理上的数组」里还原出来的标准第一步，邻接表建图、并查集前的编号映射走的都是同一套路子。

递归函数要先把契约写成一句话（「返回以我为根的子树的和」），再照着契约写代码。契约清楚了，出口、累加位置、返回值都是被推导出来的，而不是试出来的。

树形 DFS 不需要 visited，图形 DFS 需要。判断依据是「同一个节点是否可能从多条路径到达」。面试里主动说明这一点，比默默不写标记更能体现你分清了结构。

求和从自身开始、下属靠递归返回值累加，这种「自底向上聚合」的写法可以直接迁移到子树节点数、子树最大值、子树高度等一大类问题上，只需替换聚合方式。

面试视角：常见追问有三个——「如果关系里可能有环怎么办」（加 visited 集合）、「树很深会不会栈溢出」（改用显式栈或队列的迭代版 BFS/DFS）、「如果要频繁查询不同 id 怎么办」（可以做记忆化，把每个子树的和缓存下来）。提前准备好这三条能显著拉开差距。

易错点总结

错误写法：不建哈希表，每次展开下属都在员工列表里线性查找；用例员工数达到上限且汇报关系是一条长链 → 每次查找 $O(n)$、共查 $O(n)$ 次，整体 $O(n^2)$，大数据下超时。

错误写法：递归里只累加下属的重要度，忘记加上自身；用例 employees = [[1,5,[2]], [2,3,[]]]、id = 1 → 返回 3，正确答案是 8。

错误写法：递归里把自身重要度加了两次（比如既在函数开头加、又在父调用里额外加一次）；用例 employees = [[1,5,[2]], [2,3,[]]]、id = 1 → 返回 11 或 13 之类，正确答案是 8。

错误写法：从列表的第一个员工开始遍历而不是从给定 id 开始；用例 employees = [[1,5,[2]], [2,3,[]]]、id = 2 → 返回 8（把上级也算了进去），正确答案是 3。

错误写法：把整个列表的重要度直接求和；用例 employees = [[1,5,[]], [2,3,[]]]、id = 1 → 返回 8，而两人之间并无汇报关系，正确答案是 5。

错误写法：用数组 int[maxId] 代替哈希表做映射；用例员工 id 为 $10^9$ 级别或稀疏分布 → 内存溢出，或数组开不下直接崩溃。

错误写法：为「防止重复」给树形 DFS 加了 visited 却把标记打在了错误的时机（先标记父节点再遍历，却在回溯时清除）；用例任意树 → 逻辑上无害但徒增复杂度；若清除时机写错，兄弟子树共享的标记会让部分下属被跳过，结果偏小。

错误写法：改写成 BFS 时只把直接下属入队、却忘记继续把下属的下属入队；用例三层汇报关系 → 只统计到第二层，深层员工的重要度全部丢失。

错误写法：假设 id 从 1 连续编号并据此用 employees.get(id - 1) 取记录；用例 employees = [[3,5,[]], [1,2,[]]]、id = 3 → 取到的是错误的记录，返回值与目标员工无关。

错误写法：把成员变量的哈希表在多次调用之间复用却不清空（力扣同一实例可能被多组数据调用）；用例连续两组测试 → 上一组的员工记录残留，若 id 冲突则读到过期数据，结果不可预测。

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	同为自底向上聚合，但聚合方式是取最大值加一而非求和，且节点直接持有孩子指针
559. N 叉树的最大深度	简单	分支数不定，要在孩子列表上循环取最优，结构与本题最接近但无需建索引
200. 岛屿数量	中等	图形 DFS 的对照组：同一格子可从多个方向到达，必须靠 `visited` 防重复