友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
834. 树中距离之和
给定一个无向、连通的树。树中有 n 个标记为 0…n-1 的节点以及 n-1 条边。
给定整数 n 和数组 edges ， edges[i] = [ai, bi] 表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10] 解释: 树如图所示。 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
示例 2:
输入: n = 1, edges = [] 输出: [0]
示例 3:
输入: n = 2, edges = [[1,0]] 输出: [1,1]
提示:
-
1 <= n <= 3 * 104 -
edges.length == n - 1 -
edges[i].length == 2 -
0 <= ai, bi < n -
ai != bi -
给定的输入保证为有效的树
思路分析
每次将图都“转化”成一棵以起点为根的多叉树。对树做深度优先遍历，即可计算所需要的距离之和。可惜会超时！
-
一刷
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* DFS： 64 / 74 超时
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-23 21:52:43
*/
int distance = 0;
public int[] sumOfDistancesInTree(int n, int[][] edges) {
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
int[] result = new int[n];
for (int i = 0; i < n; i++) {
distance = 0;
dfs(i, graph, 0, new HashSet<>());
result[i] = distance;
}
return result;
}
private void dfs(int i, List<Integer>[] graph,
int levle, Set<Integer> used) {
if (used.contains(i)) {
return;
}
used.add(i);
distance += levle;
Set<Integer> nodes = new HashSet<>(graph[i]);
nodes.removeAll(used);
if (nodes.isEmpty()) {
return;
}
for (Integer node : nodes) {
dfs(node, graph, levle + 1, used);
}
}