分析

• 本题的考点：哈希表、DFS。

• 因为是上下级关系，因此不可能存在环，深度优先遍历过程中不需要判重。在DFS中记录答案即可。

• 使用哈希表记录每个员工的下属，这样可以方便遍历，类似于邻接表。

代码

• C++

class Solution {
public:
    unordered_map<int, Employee *> hash;  // (id, id对应员工)

    int getImportance(vector<Employee *> employees, int id) {
        for (auto &p : employees) hash[p->id] = p;
        return dfs(id);
    }

    int dfs(int id) {
        auto p = hash[id];
        int res = p->importance;
        for (auto son : p->subordinates)
            res += dfs(son);
        return res;
    }
};

• Java

class Solution {
    HashMap<Integer, Employee> hash = new HashMap<>();

    public int getImportance(List<Employee> employees, int id) {
        for (Employee p : employees) hash.put(p.id, p);
        return dfs(id);
    }

    private int dfs(int id) {
        Employee p = hash.get(id);
        int res = p.importance;
        for (int son : p.subordinates)
            res += dfs(son);
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n是员工数目。

• 空间复杂度：与遍历深度有关。