樹形動态規劃記錄

題目

[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])