題目敘述
題目給定一棵二元樹，整棵樹剛好有n個節點 和 總共n枚金幣。
每個節點的值代表該節點初始擁有金幣的數量。
每回合可以給周圍的節點一枚金幣，請問最少需要幾回合才能讓所有節點恰好擁有一枚金幣?
原本的英文題目敘述
測試範例
Example 1:
Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
Example 2:
Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
Constraints:
- The number of nodes in the tree is
n.
節點總數目為n。
1 <= n <= 100
節點總數木n 介於1~100之間。
0 <= Node.val <= n
節點擁有的金幣數量介於0~n
- The sum of all
Node.valisn.
整棵樹整共擁有n枚金幣。
演算法 收入支出平衡 + DFS模擬
根據題意，最終目標是每個節點一枚金幣，可以想成是人人有獎，而且剛好都有一枚。
題目又保證整棵樹有n個節點，有n枚金幣，所以一定有解。
可以這樣想:
統計每個節點(每個人)的收入與支出分數值:
= 原本擁有的金幣數量 + 左子樹的收入支出分數 + 右子樹的收入支出分數 - 1
-1 是為了最後保留一枚金幣給自己(當下這個節點)
如果是正值，代表這個節點所代表的子樹還有多餘的金幣可以分給別人。
如果是負值，代表這個節點所代表的子樹有不足，需有別的節點分配多餘的金幣過來。
數量就代表多幾枚金幣或少幾枚金幣。
回合數就是左子樹的分數絕對值 + 右子樹的分數絕對值。
為什麼?
因為每回合可以移動一枚金幣，
有多幾枚就需要幾回合去給出去，有少幾枚就需要幾回合拿進來。
程式碼 收入支出平衡 + DFS模擬
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
def accounting(node):
## Base case: empty node or empty tree has 0 coin
if not node:
return 0
## General cases: check and move based on balance of coins
# Check balance of left subtree
left = accounting( node.left )
# Check balance of right subtree
right = accounting( node.right )
# current move = get extra coins, and dispatch to who need coin
accounting.move += abs(left) + abs(right)
# balance of current node
# -1 term is to reserve one coin for myself
return node.val + left + right - 1
# ----------------------------------
accounting.move = 0
accounting(root)
return accounting.move
複雜度分析
時間複雜度: O(n )
DFS拜訪整棵樹，每個節點至多拜訪一次。
空間複雜度: O(n )
DFS拜訪整棵樹，當整棵樹向左歪斜或向右歪斜時。有最大深度O(n)。
關鍵知識點
根據題意推敲出，關鍵在於統計每個節點的支出收入平衡分數，分數多少，就需要對應的回合數去移動金幣。
