好几种写法，这里贴几个出来
第一种：暴力解法，除去递归栈，空间复杂度O(1)。时间复杂度略高
/*
// 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;
};
*/ static int wing=[]()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return ;
}(); class Solution
{
public:
int getImportance(vector<Employee*> employees, int id)
{
return getsum(employees,id);
} int getsum(vector<Employee*>employees,int id)
{
Employee * cur;
int cursum=;
for(auto p:employees)
{
if(p->id==id)
{
cur=p;
cursum+=p->importance;
break;
}
}
if(!(cur->subordinates.empty()))
{
for(auto subid:cur->subordinates)
cursum+=getsum(employees,subid);
}
return cursum;
}
};
第二种：用关联容器，速度快一丢丢，但是空间复杂度高一丢丢
/*
// 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;
};
*/ static int wing=[]()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return ;
}(); class Solution
{
public:
int getImportance(vector<Employee*> employees, int id)
{
unordered_map<int,Employee*> iemap;
for(auto i:employees)
iemap[i->id]=i;
return getsum(iemap,id);
} int getsum(unordered_map<int,Employee*> & emap,int id)
{
int cursum=emap[id]->importance;
for(auto e:emap[id]->subordinates)
cursum+=getsum(emap,e);
return cursum;
}
};
第三种，用数组，空间复杂度比map高些，但是速度更快
/*
// 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;
};
*/ static int wing=[]()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return ;
}(); class Solution
{
public:
int getImportance(vector<Employee*> employees, int id)
{
Employee* ptr[]={nullptr};
for(auto p:employees)
ptr[p->id]=p;
return getsum(ptr,id);
} int getsum(Employee* (&ptr)[],int id)
{
int cursum=ptr[id]->importance;
for(auto e:ptr[id]->subordinates)
cursum+=getsum(ptr,e);
return cursum;
}
};
三种方法都可以，都用了递归