人人有獎 在二元樹中分配硬幣(圖論應用) Leetcode #979

Art Rachen on Unsplash

題目敘述

題目給定一棵二元樹，整棵樹剛好有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.val is n.

整棵樹整共擁有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)。

關鍵知識點

根據題意推敲出，關鍵在於統計每個節點的支出收入平衡分數，分數多少，就需要對應的回合數去移動金幣。

Reference

[1] Distribute Coins in Binary Tree - LeetCode