1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
int maxTime = 0;
queue<int> nodes;
for(int i = 0; i < informTime.size(); i++)
{
if(informTime[i] == 0)
{
nodes.push(i);
}
}
while(!nodes.empty())
{
int node = nodes.front();
nodes.pop();
int time = 0;
while(manager[node] != -1)
{
time += informTime[manager[node]];
node = manager[node];
}
maxTime = max(time, maxTime);
}
return maxTime;
}
};
|
这个树的组织形式有别于其他的二叉树，子知其父而父不知其子，所以从底部入手更简单。
想了一下，队列好像没特别有必要，当成数组用了。
可以用记忆化搜索继续优化，但是懒得算了。