問題（Easy）：
You are given a data structure of employee information, which includes the employee's unique id, his importance value and his direct subordinates' id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.Note:
- One employee has at most one direct leader and may have several subordinates.
- The maximum number of employees won't exceed 2000.
大意：
給你一個(gè)雇員信息的數(shù)據(jù)結(jié)構(gòu)熄诡，包含雇員的唯一id、他的重要值以及他指數(shù)下級(jí)的id诗力。
比如凰浮，雇員1是雇員2的領(lǐng)導(dǎo)，雇員2是雇員3的領(lǐng)導(dǎo)苇本，他們的重要值分別為15袜茧、10和5。那么雇員1就有數(shù)據(jù)結(jié)構(gòu)[1, 15, [2]]瓣窄，雇員2是[2, 10, [3]]笛厦，雇員3是[3, 5, []]。注意即使雇員3也是雇員1的下屬俺夕，但關(guān)系不是直接的裳凸。
現(xiàn)在給出一個(gè)公司的雇員信息，和一個(gè)雇員id劝贸，你需要返回該雇員及他的下屬的總重要值姨谷。
例1：
輸入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
輸出：11
解釋：
雇員1有重要值5，他有兩個(gè)直接下屬：雇員2和雇員3映九。他們都有重要值3梦湘，因此雇員1的總重要值是5 + 3 + 3 = 11。注意：
- 一個(gè)雇員最多有一個(gè)直接領(lǐng)導(dǎo)件甥，但可能有多個(gè)下屬捌议。
- 雇員的最大數(shù)量不超過2000。
思路：
乍一看有點(diǎn)麻煩引有，但其實(shí)只是數(shù)據(jù)結(jié)構(gòu)不再是簡單數(shù)據(jù)類型了禁灼，其實(shí)還是個(gè)遞歸的解法，先根據(jù)目標(biāo)id找到雇員轿曙，記錄他的重要值弄捕，然后再對其所有下屬使用遞歸計(jì)算僻孝，這樣其下屬的下屬也會(huì)被記錄重要值，遞歸中把所有重要值都加起來就可以了守谓。
代碼（C++）：
/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
int res = 0;
for (Employee* employee : employees) {
if (employee->id == id) {
res += employee->importance;
if (employee->subordinates.size() != 0) {
for (int subId : employee->subordinates) {
res = res + getImportance(employees, subId);
}
}
break;
}
}
return res;
}
};
合集：https://github.com/Cloudox/LeetCode-Record
