员工的重要性 图解题解

这道题到底在问什么

输入

employees=[[1,5,[2,3]],[2,3,[]],[3,3,[]]], id=1

输出

11（员工 1 自己 5，下属 2 和 3 各 3，合计 5+3+3=11）

最优解：一步一步想明白

1. 3记住两句：先建哈希表凭编号秒查到人；再用深度优先，自己的重要度加上所有下属子树的重要度。
2. 4目标：从 11 号员工往下求总重要度先看清这张图。每个圆圈是一名员工，圈里的大数字是他的编号 id，旁边的小数字是他的重要度。11 号是大老板，他带着 23 号和 37 号两个直系下属；23 号自己又带 42 号和 56 号，37 号带一个 68 号，最下面这三位没有下属。题目要的是从 11 号出发，把他自己加上手下所有人，一层一层全部算到底的重要度总和。提前剧透一下，这个答案是 39，下面我们一步一步把它累出来。
3. 5哈希表：11→… 23→… 37→… 42→… 56→… 68→…动手之前有一个关键准备。下属在数据里只给了编号，比如 11 号手下是 23 号和 37 号，光有编号还不够，我们得能凭编号立刻找到那个人的重要度和他自己的下属名单。注意这些编号是 11、23、37 这种不连续的数，不能拿编号直接当数组下标去取。所以先扫一遍所有员工，建一张哈希表，把每个编号映射到对应的员工记录。建好之后，无论手里拿到哪个编号，一步就能查到人，这一步是 O(1)，整张表建好是 O(n)。
4. 6栈：11 号 累计 = 0正式开始遍历。我们用一个栈来模拟深度优先搜索，把起点 11 号压进栈，累计总和先记为 0。盯住右边两块面板：上面是待访问员工栈，栈顶在最上面，是下一个要处理的人；下面是已经累加进答案的重要度序列。接下来只重复一个动作：弹出栈顶、查到这个人、把他的重要度加进总和、再把他的直系下属压回栈，直到栈空。
5. 7栈顶 = 11 号 累计 = 0栈里现在只有 11 号，他就是栈顶。深度优先搜索的第一步永远是处理起点自己，所以下一帧把他弹出来累加。
6. 8累计 = 5弹出栈顶 11 号，凭编号在哈希表里查到他，重要度是 5，加进总和。累计从 0 变成 5。处理完一个人，紧接着要把他的直系下属安排上。
7. 9栈顶 = 23 号 累计 = 511 号有两个直系下属 23 号和 37 号，把他们压回栈。这里有个讲究：逆序压，先压右边的 37 号、再压左边的 23 号，这样栈顶就是 23 号，后面会先把 23 号这一整支彻底走完，再回头处理 37 号。11 号自己已结算，变绿。
8. 10栈顶 = 23 号 累计 = 5现在栈顶是 23 号，37 号在他下面排队等着。深度优先的意思就是先一头扎到底，把 23 号这一支连同他的下属全部走完，才轮到 37 号。
9. 11累计 = 13弹出 23 号，哈希表查到他重要度 8，加进总和，累计从 5 变成 13。23 号手下还有人，继续安排他的下属。
10. 12栈顶 = 42 号 累计 = 1323 号带着 42 号和 56 号两个下属，同样逆序压栈：先压 56 号、再压 42 号，于是栈顶变成 42 号。此刻栈里从顶到底是 42 号、56 号、37 号，正好等着按这个顺序处理。23 号结算变绿。
11. 13栈顶 = 42 号 累计 = 13栈顶是 42 号，他是 23 号的第一个下属。
12. 14累计 = 17弹出 42 号，重要度 4 加进总和，累计从 13 变成 17。
13. 1542 号处理完 累计 = 1742 号手下没有任何人，是棵子树的叶子，他这一支到此为止，直接结算，节点变绿。
14. 16栈顶 = 56 号 累计 = 17栈顶轮到 56 号，他是 23 号的第二个下属。
15. 17累计 = 24弹出 56 号，重要度 7 加进总和，累计从 17 变成 24。到这里，23 号手下的两个人 42 号、56 号都算过了。
16. 1856 号处理完 累计 = 2456 号也没有下属，结算变绿。23 号这一整支就彻底走完了，现在回头处理一直在栈底等着的 37 号。
17. 19栈顶 = 37 号 累计 = 24栈顶现在是 37 号，他是大老板 11 号的第二个直系下属，刚才一直在栈底耐心排队。
18. 20累计 = 30弹出 37 号，重要度 6 加进总和，累计从 24 变成 30。37 号手下还有人，继续安排。
19. 21栈顶 = 68 号 累计 = 3037 号只有一个下属 68 号，把他压回栈，栈顶变成 68 号。37 号结算变绿。
20. 22栈顶 = 68 号 累计 = 30栈里只剩 68 号，他是 37 号唯一的下属，也是整张图最后一个没处理的人。
21. 23累计 = 39弹出 68 号，重要度 9 加进总和，累计从 30 变成 39。这时栈空了。
22. 2468 号处理完 累计 = 3968 号没有下属，结算变绿。栈已经清空，整趟深度优先搜索到此结束。
23. 25答案：累计 = 39所有人都处理过了，全部变绿。看累计总和，正好是 39。我们把它拆开验证一遍：大老板 11 号自己 5，加上 23 号那一支的 8 加 4 加 7 等于 19，再加上 37 号那一支的 6 加 9 等于 15，合起来 5 加 19 加 15 就是 39。整个过程靠一张哈希表凭编号秒查到人，再用深度优先一路扎到底逐个累加，每个人只走一遍，干净利落。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
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 = {e.id: e for e in employees}
        def dfs(x):
            e = mp[x]
            return e.importance + sum(dfs(y) for y in e.subordinates)
        return dfs(id)

#include <iostream>
#include <unordered_map>
#include <vector>
#include <functional>
using namespace std;
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> mp;
        for (auto e : employees) mp[e->id] = e;
        function<int(int)> dfs = [&](int x) {
            auto e = mp[x];
            int ans = e->importance;
            for (int y : e->subordinates) ans += dfs(y);
            return ans;
        };
        return dfs(id);
    }
};

import java.util.*;
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> mp = new HashMap<>();
        for (Employee e : employees) mp.put(e.id, e);
        return dfs(mp, id);
    }
    private int dfs(Map<Integer, Employee> mp, int id) {
        Employee e = mp.get(id);
        int ans = e.importance;
        for (int sub : e.subordinates) ans += dfs(mp, sub);
        return ans;
    }
}

复杂度

面试官可能追问