0834. Sum of Distances in Tree

题目信息

题号:

0834

难度:

Hard

主题:

树、节点距离、全节点结果

原题:

LeetCode 0834

重点:

对每个节点分别求它到全部节点的最短边数之和;输入是无向连通树,节点自身距离为零

题目重述

给定一棵包含 n 个节点的无向树,节点编号为 0 至 n - 1,数组 edges 中每项 [a, b] 表示节点 a 与 b 之间有一条边。

树中两个节点之间的距离等于连接它们的唯一路径所经过的边数。请返回长度为 n 的数组 answer,其中 answer[i] 是节点 i 到所有 n 个节点的距离之和;节点到自身的距离为 0。

1 <= n <= 3 * 10^4,edges.length == n - 1,每条边连接两个不同的合法节点,输入保证构成一棵无向连通树。

自建示例

四个节点组成一条链:

输入:n = 4, edges = [[0,1],[1,2],[2,3]]
输出:[6,4,4,6]
解释:节点 0 到各节点距离为 0、1、2、3,总和 6;节点 1 的距离为 1、0、1、2,总和 4,另外两个节点对称。

树只有一个节点:

输入:n = 1, edges = []
输出:[0]
解释:n 达到题目允许的最小值,树没有边。唯一节点只需计算到自身的距离 0,因此结果为 [0]。