LeetCode 690. 员工的重要性

字数 1683 2025-12-16 13:57:51

LeetCode 690. 员工的重要性

题目描述

你需要计算一个员工及其所有下属（直接和间接）的重要性之和。题目给定以下数据结构：

一个员工信息的列表。每个员工信息是一个包含三个元素的类：id（员工唯一ID，为整数）、importance（该员工的重要性值，为整数）、subordinates（该员工的直接下属的ID列表）。
一个指定的员工ID。

你需要返回以这个指定员工为根节点的子树中，所有员工的重要性值之和。

解题过程循序渐进讲解

理解输入与数据结构
- 题目输入是一个员工信息的列表，列表中的每个元素是一个Employee对象。为了方便查找，我们通常会将这个列表转换为一个从id映射到员工对象的字典（哈希表）。
- 这样，给定任何一个员工的ID，我们都可以立即找到他的importance和subordinates列表。
问题本质
- 这个问题可以抽象为一个树形结构的遍历问题。每个员工是一个节点，其subordinates列表里存储的是其直接子节点的ID。
- 我们需要计算的是，给定一个根节点（指定的员工ID），求这棵子树所有节点值的和（即重要性之和）。
- 这明显是一个树/图的搜索（遍历）问题。由于下属关系是单向的（不会出现循环依赖），所以我们可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来遍历所有相关节点。
算法步骤详解（以DFS为例）
- 步骤1：构建映射
  遍历给定的员工列表，以每个员工的id为键，员工对象本身为值，存入一个字典（如Python的dict）。这样我们就有了一个快速查询表id_to_employee。
```
映射示例：
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]]
构建的字典: {1: Employee(1,5,[2,3]), 2: Employee(2,3,[]), 3: Employee(3,3,[])}
```
- 步骤2：定义递归DFS函数
  这个函数的目标是计算以某个员工eid为根的子树的总重要性。
  1. 从id_to_employee字典中，取出ID为eid的员工对象emp。
  2. 初始化总和total为当前员工的重要性值：emp.importance。
  3. 遍历当前员工的直接下属ID列表emp.subordinates：
    - 对每一个下属IDsub_id，递归调用DFS函数，计算以其为根的子树重要性总和，并将结果累加到total上。
  4. 递归函数返回total。
- 步骤3：启动与返回
  以题目给定的id作为参数，调用步骤2中定义的DFS函数，其返回值即为最终答案。
为什么可以不用visited集合？
- 因为题目给出的员工关系结构是一棵树（或有向无环图）。每个员工只有一个直接上级（从下属ID列表中可以看出，一个员工可能出现在多个下属列表中吗？不会，因为题目定义subordinates是直接下属的ID，整个结构是树形，没有环），所以在深度优先遍历中，不会重复访问同一个节点，因此不需要visited集合来记录已访问节点。
复杂度分析
- 时间复杂度：O(N)，其中N是员工数量。在最坏情况下，我们需要访问所有员工一次。
- 空间复杂度：O(N)，主要用于存储ID到员工的映射字典。递归调用栈的深度取决于树的高度，在最坏情况下（链表状的树）深度也为O(N)。
BFS解法思路
- 除了DFS，我们也可以使用BFS（队列）来层序遍历这棵树。
- 步骤：
  1. 同样构建id_to_employee映射。
  2. 初始化一个队列，将给定的员工ID加入队列。
  3. 初始化总和total_importance = 0。
  4. 当队列不为空时：
    - 弹出队首的IDcurrent_id。
    - 通过映射获取该员工对象emp。
    - 将emp.importance累加到total_importance。
    - 将emp.subordinates中的所有下属ID依次加入队列。
  5. 遍历结束后，返回total_importance。
- BFS同样能访问到所有下属，并且是按层级访问的。

总结
这道题的核心是将给定的列表数据转换为易于查询的结构（哈希表），然后通过简单的树遍历（DFS或BFS）来累积重要性值。它考察了对基本数据结构的操作和对树/图遍历的应用，是搜索算法中一个非常典型的入门题目。

LeetCode 690. 员工的重要性题目描述你需要计算一个员工及其所有下属（直接和间接）的重要性之和。题目给定以下数据结构：一个员工信息的列表。每个员工信息是一个包含三个元素的类： id （员工唯一ID，为整数）、 importance （该员工的重要性值，为整数）、 subordinates （该员工的直接下属的ID列表）。一个指定的员工ID。你需要返回以这个指定员工为根节点的子树中，所有员工的重要性值之和。解题过程循序渐进讲解理解输入与数据结构题目输入是一个员工信息的列表，列表中的每个元素是一个 Employee 对象。为了方便查找，我们通常会将这个列表转换为一个从 id 映射到员工对象的字典（哈希表）。这样，给定任何一个员工的ID，我们都可以立即找到他的 importance 和 subordinates 列表。问题本质这个问题可以抽象为一个树形结构的遍历问题。每个员工是一个节点，其 subordinates 列表里存储的是其直接子节点的ID。我们需要计算的是，给定一个根节点（指定的员工ID），求这棵子树所有节点值的和（即重要性之和）。这明显是一个树/图的搜索（遍历）问题。由于下属关系是单向的（不会出现循环依赖），所以我们可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来遍历所有相关节点。算法步骤详解（以DFS为例）步骤1：构建映射遍历给定的员工列表，以每个员工的 id 为键，员工对象本身为值，存入一个字典（如Python的 dict ）。这样我们就有了一个快速查询表 id_to_employee 。步骤2：定义递归DFS函数这个函数的目标是计算以某个员工 eid 为根的子树的总重要性。从 id_to_employee 字典中，取出ID为 eid 的员工对象 emp 。初始化总和 total 为当前员工的重要性值： emp.importance 。遍历当前员工的直接下属ID列表 emp.subordinates ：对每一个下属ID sub_id ，递归调用DFS函数，计算以其为根的子树重要性总和，并将结果累加到 total 上。递归函数返回 total 。步骤3：启动与返回以题目给定的 id 作为参数，调用步骤2中定义的DFS函数，其返回值即为最终答案。为什么可以不用visited集合？因为题目给出的员工关系结构是一棵树（或有向无环图）。每个员工只有一个直接上级（从下属ID列表中可以看出，一个员工可能出现在多个下属列表中吗？不会，因为题目定义 subordinates 是直接下属的ID，整个结构是树形，没有环），所以在深度优先遍历中，不会重复访问同一个节点，因此不需要 visited 集合来记录已访问节点。复杂度分析时间复杂度：O(N) ，其中N是员工数量。在最坏情况下，我们需要访问所有员工一次。空间复杂度：O(N) ，主要用于存储ID到员工的映射字典。递归调用栈的深度取决于树的高度，在最坏情况下（链表状的树）深度也为O(N)。 BFS解法思路除了DFS，我们也可以使用BFS（队列）来层序遍历这棵树。步骤：同样构建 id_to_employee 映射。初始化一个队列，将给定的员工ID加入队列。初始化总和 total_importance = 0 。当队列不为空时：弹出队首的ID current_id 。通过映射获取该员工对象 emp 。将 emp.importance 累加到 total_importance 。将 emp.subordinates 中的所有下属ID依次加入队列。遍历结束后，返回 total_importance 。 BFS同样能访问到所有下属，并且是按层级访问的。总结这道题的核心是将给定的列表数据转换为易于查询的结构（哈希表），然后通过简单的树遍历（DFS或BFS）来累积重要性值。它考察了对基本数据结构的操作和对树/图遍历的应用，是搜索算法中一个非常典型的入门题目。