树形动态规划记录

题目

[834. 树中距离之和]——HARD

834. 树中距离之和

给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边 。

第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。

返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

示例 1:

输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]

输出: [8,12,6,10,10,10]

解释:

如下为给定的树的示意图：

0
 / \
1   2
   /|\
  3 4 5
           

我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)

也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。

说明: 1 <= N <= 10000

通过次数8,718提交次数16,844

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sum-of-distances-in-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

[834. 树中距离之和]

1. 遍历+动态规划

   https://leetcode-cn.com/problems/sum-of-distances-in-tree/solution/shou-hua-tu-jie-shu-zhong-ju-chi-zhi-he-shu-xing-d/

preOrder：

因此还需要计算每个子树的节点个数nodeNum[i]，递归公式如下：

• n o d e N u m [ r o o t ] = s u m ( n o d e N u m [ c h i l d ] ) + 1 nodeNum[root] = sum(nodeNum[child])+1 nodeNum[root]=sum(nodeNum[child])+1
• d i s t S u m [ r o o t ] = s u m ( n o d e N u m [ c h i l d ] + d i s t S u m [ c h i l d ] ) distSum[root] = sum(nodeNum[child] + distSum[child]) distSum[root]=sum(nodeNum[child]+distSum[child])

从上往下递归，到达底部就遇到「结果已知的 base case」，随着递归的出栈，结果不断向上返回，最后求出当前子树的 distSum。

postOrder：

• 此时的distSum数组，存放 root 到所在子树中的节点的距离和，显然，还要加上子树外的节点到 root 的距离和，才是最后的结果。

  

  如上图，节点2所在的子树的节点个数为nodeNum[2]，这nodeNum[2]个节点，从计算distSum[0]变成计算distSum[2]：从节点

  0 到这些节点，变成从节点 2 到这些节点，每个节点都少走了一步，一共少走了nodeNum[2]步。

• 子树以外的节点呢，有N - nodeNum[2]个，从计算distSum[0]变成计算distSum[2]：从节点 0 到这些节点，变成从节点 2 到这些节点，每个节点都多走了一步，一共多走了N-nodeNum[2]步。
• 所以，我们找到distSum[i]与distSum[root]之间的递推关系： d i s t S u m [ i ] = d i s t S u m [ r o o t ] − n o d e N u m [ i ] + ( N − n o d e N u m [ i ] ) distSum[i] = distSum[root] - nodeNum[i] + (N - nodeNum[i]) distSum[i]=distSum[root]−nodeNum[i]+(N−nodeNum[i]) d i s t S u m [ i ] = d i s t S u m [ r o o t ] − n o d e N u m [ i ] + ( N − n o d e N u m [ i ] ) distSum[i]=distSum[root]−nodeNum[i]+(N−nodeNum[i]) distSum[i]=distSum[root]−nodeNum[i]+(N−nodeNum[i])