題目

給定一個有 N 個結點的二叉樹的根結點 root，樹中的每個結點上都對應有 node.val 枚硬幣，

並且總共有 N 枚硬幣。

在一次移動中，我們可以選擇兩個相鄰的結點，然後將一枚硬幣從其中一個結點移動到另一個結點。

(移動可以是從父結點到子結點，或者從子結點移動到父結點。)。

返回使每個結點上只有一枚硬幣所需的移動次數。

示例 1：輸入：[3,0,0] 輸出：2

解釋：從樹的根結點開始，我們將一枚硬幣移到它的左子結點上，一枚硬幣移到它的右子結點上。

示例 2：輸入：[0,3,0] 輸出：3

解釋：從根結點的左子結點開始，我們將兩枚硬幣移到根結點上 [移動兩次]。

然後，我們把一枚硬幣從根結點移到右子結點上。

示例 3：輸入：[1,0,2] 輸出：2

示例 4：輸入：[1,0,0,null,3] 輸出：4

提示：1<= N <= 100

0 <= node.val <= N

解題思路分析

1、遞迴；時間複雜度O(n)，空間複雜度O(log(n))

var res intfunc distributeCoins(root *TreeNode) int {	res = 0	dfs(root)	return res}func dfs(root *TreeNode) int { // 該節點子樹多餘/需要金幣數量	if root == nil {		return 0	}	left := dfs(root.Left)	right := dfs(root.Right)	res = res + abs(left) + abs(right)	return left + right + root.Val - 1}func abs(a int) int {	if a < 0 {		return -a	}	return a}

總結

Medium題目，二叉樹題目，統計每一個節點多餘或者需要金幣的數量，當前節點的金幣數量等於左右節點數量+當前節點數量-1