690. 员工的重要性
题目描述
输入员工信息数组 employees。每个员工用 [id, importance, subordinates] 表示：id 是唯一编号，importance 是重要度，subordinates 是其直接下属的编号列表。
再给一个员工编号 id。计算这名员工本人加上他所有下属（包括下属的下属，层层往下）的重要度之和并返回。
示例 1
输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1 输出：11
解释：员工 1 的重要度为 5，两名直接下属各为 3，合计 11。
示例 2
输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5 输出：-3
解释：员工 5 没有下属，结果就是他自己的 -3。
数据范围
1 <= employees.length <= 20001 <= employees[i].id <= 2000- 所有员工的
id各不相同。 -100 <= employees[i].importance <= 100- 每名员工至多有一位直接上级，可以有多名下属。
subordinates中的编号都对应真实存在的员工。
解题思路
下属关系构成一棵以给定员工为根的树（整体是森林）。先用哈希表把 id 映射到员工对象，这样按 id 找人是 O(1)。然后从给定 id 出发做 DFS（这里用显式栈）：每弹出一个 id，就把这个员工的重要度加进总和，再把他的直系下属 id 全部压栈。栈空时就遍历完了整棵子树。
为什么正确
栈里放的是“已发现、还没累加”的员工；每个员工只有一个直属上级，所以每人恰好入栈一次，不会重复累加。
复杂度分析
时间 O(n)，建表和遍历各访问每个员工一次；空间 O(n)，哈希表和栈。
易错点
subordinates 里只有 id，不是员工对象，要先建哈希表再查；在列表里线性查找会退化成 O(n²)。另外只统计给定员工那棵子树，列表里其他人（例如别的部门、他的上级）不能算进去。员工链可能很深（2000 层），Python 递归会超过默认深度，用显式栈更稳妥。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getImportance(self, employees: List['Employee'], id: int) -> int:
emp = {e.id: e for e in employees}
total = 0
stack = [id]
while stack:
cur = emp[stack.pop()]
total += cur.importance
for s in cur.subordinates:
stack.append(s)
return totalclass Solution {
public int getImportance(List<Employee> employees, int id) {
Map<Integer, Employee> emp = new HashMap<>();
for (Employee e : employees) emp.put(e.id, e);
int total = 0;
Deque<Integer> st = new ArrayDeque<>();
st.push(id);
while (!st.isEmpty()) {
Employee cur = emp.get(st.pop());
total += cur.importance;
for (int s : cur.subordinates)
st.push(s);
}
return total;
}
}class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
unordered_map<int, Employee*> emp;
for (auto e : employees) emp[e->id] = e;
int total = 0;
vector<int> st{id};
while (!st.empty()) {
Employee* cur = emp[st.back()]; st.pop_back();
total += cur->importance;
for (int s : cur->subordinates)
st.push_back(s);
}
return total;
}
};func getImportance(employees []*Employee, id int) int {
emp := map[int]*Employee{}
for _, e := range employees {
emp[e.Id] = e
}
total := 0
st := []int{id}
for len(st) > 0 {
cur := emp[st[len(st)-1]]
st = st[:len(st)-1]
total += cur.Importance
for _, s := range cur.Subordinates {
st = append(st, s)
}
}
return total
}var GetImportance = function(employees, id) {
const emp = new Map();
for (const e of employees) emp.set(e.id, e);
let total = 0;
const st = [id];
while (st.length) {
const cur = emp.get(st.pop());
total += cur.importance;
for (const s of cur.subordinates)
st.push(s);
}
return total;
};function getImportance(employees: Employee[], id: number): number {
const emp = new Map<number, Employee>();
for (const e of employees) emp.set(e.id, e);
let total = 0;
const st: number[] = [id];
while (st.length) {
const cur = emp.get(st.pop()!)!;
total += cur.importance;
for (const s of cur.subordinates)
st.push(s);
}
return total;
};