Distribute Coins in Binary Tree

Photo by Steve Johnson on Unsplash
Photo by Steve Johnson on Unsplash

Problem

你有一個 n 個節點(node)的二元樹 root,每個在二元樹上的 node 有 node.val 枚硬幣,整個二元樹總共有 n 枚硬幣。 在每一次的移動中,我們需要選擇兩個相鄰的 node 並且移動一枚硬幣到另一個 node。移動的方式可能是從 parent node 移動到 child node,或者是 child node 到 parent node。回傳讓每個 node 都有一枚硬幣所需要的最小移動次數。

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.
  • 1 <= n <= 100
  • 0 <= Node.val <= n
  • The sum of all Node.val is n.

Solution

一開始看到這個題目的時候的想法是從二元樹的節點出發去思考,怎麼往下去分配硬幣,但看到 Example 2 的時候就發現自己的想法錯了,因為根節點可能會是沒有任何的硬幣的,那麼該要怎麼做會比較好?

如果 child node 上都沒有任何的硬幣,那代表需要由 parent node 將硬幣分給它;若 child node 有超過一個以上的硬幣,那 node 本身只需要留下一枚,剩下的需要分配到其他沒有硬幣的 node。

以範例一來說,左右的 child node 都沒有任何的硬幣,那麼就需要從 parent node 分別個移動一個硬幣到左右的 child node,所以移動的次數會是 1 + 1 = 2 次;在範例二當中,可以看到示意圖是從左邊的 child node 出發來移動硬幣,因為 parent node 本身沒有硬幣所以無法分配,根據這兩個範例可以推論出硬幣的分配是:

取決於子節點(Child Node)

根據題目要求要找到最小的移動次數,移動包含了「移入」和「移出」的動作,這些動作都被視為一次的操作

// move might be a negative number
abs(move)

透過 steps 變數來記錄每次移動的次數:

func distributeCoins(root *TreeNode) int {
steps := 0
dfs(root, &steps)
return steps
}

dfs 函式就是整個問題求解的核心。


Implementation

由於是二元樹(Binary Tree),會使用遞歸(Recursion)來解題。首先找出 Base Case,也就是當 child node 為空的時候,不需要被分配任何硬幣:

func dfs(root *TreeNode, steps *int) int {
+ if root == nil {
+ return 0
+ }
}

接著是 Recursive Case,根據題目可以使用後序遍歷(Post-Order Traversal)

func dfs(root *TreeNode, steps *int) int {
if root == nil {
return 0
}
+ left := dfs(root.Left, steps)
+ right := dfs(root.Right, steps)
// Do something...
}

以範例一作為說明搭配著圖來看,把 Do something... 的實作部分補上:

example1-first

看到左節點本身並沒有包含任何 child node,所以符合 Base Case 所以各回傳 0,也就是不需要任何的移動,可以得到以下計算:

steps = steps + abs(left) + abs(right) // 0 + 0 + 0

接著到了左節點本身,它並沒有任何的硬幣,表示它需要由父節點來分配硬幣,可以得到以下計算:

coins = root.Val - 1 + left + right // 0 - 1 + 0 + 0 = -1, -1 表示需要被分配一枚硬幣

其中 root.Val - 1 代表的意思是節點本身至少要有一枚硬幣。

example1-second

因為左右兩側節點相同,所以右節點過程會跟上述一樣,所以可以得到此推導:

example1-third

最後回到根節點,可以推導出:

// implement Do something...
left := dfs(root.Left, steps) // -1,代表需要分配一枚硬幣
right := dfs(root.Right, steps) // -1,代表需要分配一枚硬幣
steps = steps + abs(-1) + abs(-1) // 0 + 1 + 1 = 2,代表需要移動兩次
return root.Val - 1 + left + right // 3 - 1 + (-1) + (-1) = 0

這樣就完成了範例一,讓我們在花一些時間來驗證上述概念套在範例二是否也能找出答案。


範例二一樣先從左節點開始看起:

example2-first

左節點的 root.Val = 3 且沒有任何的子節點,可以計算出:

example2-first

左節點本身留一枚硬幣,接著需要移動兩次硬幣到根節點,根節點本身沒有任何硬幣,需要自己留一個,右節點也需要被分配一枚硬幣:

example2-first
left := dfs(root.Left, steps) // 3 - 1 + 0 + 0 = 2
right := dfs(root.Right, steps) // -1
steps = steps + abs(2) + abs(-1) // 0 + 2 + 1 = 3
return root.Val - 1 + left + right // 0 - 1 + 2 + (-1) = 0

完整實作

func distributeCoins(root *TreeNode) int {
steps := 0
dfs(root, &steps)
return steps
}
func dfs(root *TreeNode, steps *int) int {
if root == nil {
return 0
}
left := dfs(root.Left, steps)
right := dfs(root.Right, steps)
*steps = *steps + abs(left) + abs(right)
return root.Val - 1 + left + right
}

Reference