690. 员工的重要性

题目描述：

你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。

给定一个员工数组 employees，其中：

• employees[i].id 是第 i 个员工的 ID。
• employees[i].importance 是第 i 个员工的重要度。
• employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。

给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。

示例 1：

输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

示例 2：

输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5
输出：-3
解释：员工 5 的重要度为 -3 并且没有直接下属。
因此，员工 5 的总重要度为 -3。

提示：

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• 所有的 employees[i].id 互不相同。
• -100 <= employees[i].importance <= 100
• 一名员工最多有一名直接领导，并可能有多名下属。
• employees[i].subordinates 中的 ID 都有效。

---

解题分析及思路：

方法：深度优先搜索

思路：

采用深度优先搜索，找到该员工及其下属，将其重要度 和 下属重要度累加，若下属还有下属，则将下属的下属的重要度也累加，直到其所有的下属都遍历完成。

为了方便找到下属，可以使用哈希表存储所有的员工的信息，编号作为key。

func getImportance(employees []*Employee, id int) int {
	m := make(map[int]*Employee)
	for _, e := range employees {
		m[e.Id] = e
	}
	return dfs(m, id)
}

func dfs(m map[int]*Employee, id int) int {
	var res = m[id].Importance
	var subordinates = m[id].Subordinates
	for index := range subordinates {
		res += dfs(m, subordinates[index])
	}
	return res
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:7 ms,击败了95.24% 的Go用户
• 内存消耗:6.6 MB,击败了95.24% 的Go用户