LeetCode 834. 树中距离之和 C#
原题链接
困难
作者:
hpstory
,
2023-07-16 22:17:19
,
所有人可见
,
阅读 74
C# 代码
public class Solution {
public int[] SumOfDistancesInTree(int n, int[][] edges) {
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < n; i++) graph.Add(new List<int>());
foreach (int[] edge in edges){
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
int[] result = new int[n];
int[] count = new int[n];
Array.Fill(count, 1);
DFS1(0, -1, 0);
DFS2(0, -1);
return result;
void DFS1(int x, int fa, int depth){
result[0] += depth;
foreach (int i in graph[x]){
if (i != fa){
DFS1(i, x, depth + 1);
count[x] += count[i];
}
}
}
void DFS2(int x, int fa){
foreach (int i in graph[x]){
if (i != fa){
result[i] = result[x] + n - 2 * count[i];
DFS2(i, x);
}
}
}
}
}