690.员工的重要性

链接：690.员工的重要性
难度：Medium
标签：树、深度优先搜索、广度优先搜索、数组、哈希表
简介：现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。

题解 1 - typescript

• 编辑时间：2021-05-01
• 执行用时：80ms
• 内存消耗：42.2MB
• 编程语言：typescript
• 解法介绍：哈希表储存。

function GetImportance(employees: Employee[], id: number): number {
  const map = employees.reduce((map, emp) => {
    map.set(emp.id, emp);
    return map;
  }, new Map<number, Employee>());
  const find = (id: number): number => {
    const emp = map.get(id)!;
    return (
      emp.importance + emp.subordinates.map(id => find(id)).reduce((total, cur) => total + cur, 0)
    );
  };
  return find(id);
}

题解 2 - python

• 编辑时间：2024-08-26
• 执行用时：113ms
• 内存消耗：17.75MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        map = dict()
        for item in employees: map[item.id] = item
        def dfs(id: int) -> int: return map[id].importance + sum(dfs(id) for id in map[id].subordinates)
        return dfs(id)