员工的重要性 图解题解

给一个编号，到底要把哪些人的重要度加起来

每名员工带三样东西：唯一编号 id、一个重要度、一份直系下属的编号名单。给你一个员工编号，要返回他本人加上手下所有人的重要度总和——注意是所有人，下属的下属、一直往下到最底层都得算进去。题面例子 employees=[[1,5,[2,3]],[2,3,[]],[3,3,[]]]、id=1：1 号自己 5，两个下属 2 号、3 号各 3，合计 5+3+3=11。重要度还可能是负数，范围 -100 到 100。

顺着下属编号找人，为什么会退化成 O(n²)

下属名单里给的是编号，不是员工本身。要拿到 2 号的重要度，得先在 employees 里把 2 号那条记录捞出来。若每次都从头扫一遍数组比对编号，单次查找就是 O(n)，而整棵组织有 n 个人要查，合起来就是 O(n²)。n 到 2000 时，这多出来的一层扫描纯属白费力气。

先建一张编号到人的表，再顺着下属递归

两个动作配合。第一，建一张哈希表，也就是凭编号一步就能查到对应员工的表，键是 id、值是那名员工；建表只需把 employees 扫一遍，之后任何一次「凭编号找人」都降到 O(1)，不再回头扫数组。第二，从目标编号出发做深度优先，即顺着一条下属链一直走到底再回头：处理一个人时，先取他自己的重要度，再对他名单里的每个下属编号递归求和，两部分相加就是这个人连同整棵下属子树的总重要度。

每个节点返回的到底是什么

把递归看成一个约定：dfs(x) 交回来的，是编号 x 这个人加上他底下所有人的重要度之和。落到代码里就一行——先用哈希表查到 x 本人拿到 importance，再对他每个下属 y 调用 dfs(y)、把这些子树和累加上去。递归自然会往下钻：算 x 得先算清每个下属子树，而下属子树又要先算清它们各自的下属，一层套一层，直到碰上没有下属的人直接返回自身重要度，回程时这些值层层相加汇总回来。这样「下属的下属也要算」根本不用特意处理，递归结构本身就保证不漏人。

拿题面这三名员工顺着算下来

从 dfs(1) 起。哈希表查到 1 号重要度 5，他的下属是 2 号和 3 号，于是要算 5 + dfs(2) + dfs(3)。先看 dfs(2)：2 号重要度 3，下属名单是空的，没有人可再递归，直接返回 3。dfs(3) 同理，3 号重要度 3、名单也空，返回 3。回到 1 号这层，把三块拼起来：5 + 3 + 3 = 11，这就是 1 号的总重要度。

O(n) 之外，三种边界别想当然

建表扫一遍是 O(n)，深度优先里每个相关员工只被查到、累加一次，所有下属编号总共也只走一遍，合起来时间 O(n)；哈希表存下全部 n 个人是 O(n)，递归调用栈在组织链排成一条直线时最深也到 O(n)，空间同样 O(n)。

最常见的错是只把直系下属加进去、漏了下属的下属，题目要的是整棵子树，少算孙辈就丢掉一大片。其次是拿编号直接当数组下标取人，可编号既不连续、最大能到 2000，当下标既浪费又会越界，只能走哈希表。还有人以为重要度都是正的，就跳过或取绝对值，实际它能低到 -100，照常加减才对。

Python

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)

C++

#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);
    }
};

Java

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;
    }
}