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``,每条边连接两个不同的合法节点,输入保证构成一棵无向连通树。 自建示例 -------- 四个节点组成一条链: .. code-block:: text 输入: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,另外两个节点对称。 树只有一个节点: .. code-block:: text 输入:n = 1, edges = [] 输出:[0] 解释:n 达到题目允许的最小值,树没有边。唯一节点只需计算到自身的距离 0,因此结果为 [0]。