难度: Medium
给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。
比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。
示例：
输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 输出：11 解释： 员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。
提示：
运行时间: 103 ms
内存: 17.2 MB
"""
# Definition for Employee.
class Employee:
def __init__(self, id: int, importance: int, subordinates: List[int]):
self.id = id
self.importance = importance
self.subordinates = subordinates
"""
class Solution:
def getImportance(self, employees: List['Employee'], id: int) -> int:
mp = {employee.id : employee for employee in employees}
def dfs(id: int) -> int:
employee = mp[id]
total = employee.importance + sum(dfs(subId) for subId in employee.subordinates)
return total
return dfs(id)
本题解使用深度优先搜索（DFS）的方法，用哈希表 mp 存储员工 ID 到员工对象的映射，然后从给定的员工 ID 开始递归计算所有下属员工的重要度之和。在DFS过程中，对于每个员工，将其自身的重要度与所有直系下属的重要度相加，直到下属员工为空，然后回溯并返回总重要度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def getImportance(self, employees: List['Employee'], id: int) -> int:
# 用哈希表存储员工ID到员工对象的映射
mp = {employee.id : employee for employee in employees}
def dfs(id: int) -> int:
# 获取当前员工对象
employee = mp[id]
# 计算当前员工的重要度与所有直系下属的重要度之和
total = employee.importance + sum(dfs(subId) for subId in employee.subordinates)
return total
# 从给定的员工ID开始DFS搜索
return dfs(id)
在Python中，哈希表（即字典）的键可以是任何不可变类型，包括整数、浮点数、字符串或元组，只要这些类型是不可变的且能够被哈希化。因此，无论ID是连续还是非连续，或是整数与非整数（如字符串），使用哈希表来存储员工ID到员工对象的映射都没有特殊的考虑或限制。这使得哈希表成为存储具有不同类型键值的灵活数据结构。
是的，深度优先搜索（DFS）使用递归实现时，可能会在处理非常大的员工层级结构或非常深的递归深度时遭遇栈溢出问题，因为每一层递归调用都会消耗一定的栈空间。为避免这种情况，可以考虑使用迭代的方式实现DFS，借助显式栈来控制递归过程，或者改用广度优先搜索（BFS）来避免深层递归。另外，增加系统的栈大小也是一个可行的解决方案，但这并不总是最优的选择。
是的，如果员工的下属结构中存在环形引用，即一个员工直接或间接地成为自己的下属，则递归函数`dfs`会因为无限递归而导致栈溢出错误。为防止这种情况发生，可以在`dfs`函数中添加一个集合来跟踪已访问的员工ID。在每次递归调用前检查当前员工ID是否已在集合中，如果是，则跳过该员工，这样可以防止重复访问并避免环形递归。
题解中的代码并没有显式处理输入的员工ID不存在于员工列表中的情形。在这种情况下，尝试访问`mp[id]`将引发一个`KeyError`，因为该ID不在字典的键中。为了更健壮的错误处理，可以在访问哈希表之前加入检查，如果ID不存在于哈希表中，可以返回0或抛出一个更具体的异常，或者返回一个合理的错误信息，以更优雅地处理这种错误情况。