→ argorok: 別捲了 05/18 18:18
推 devilkool: 你們好厲害，這題我想好久不知道從何下手 05/18 18:25
→ JIWP: 我有偷看別人提示，這題好難 05/18 18:26
979. Distribute Coins in Binary Tree
有一個二元樹有n個node
每個node的value代表該node有的coin數量
總共有n個coins
每次move可以將1個coin移動掉別的node
請問最少需要請次move才可以讓所有node都剛好有一個node?
思路:
去計算每個node左、右節點需要多少個coin
並且加上node.val-1(-1代表這個node本身需要的coin)
這個數值取絕對值就是coin經過該node的次數
對每個node進行這樣的計算加起來後就是解答
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func distributeCoins(root *TreeNode) int {
res:=0
var dfs func(node *TreeNode)int
dfs=func(node *TreeNode)int{
if node==nil{
return 0
}
lval:=dfs(node.Left)
rval:=dfs(node.Right)
tmp:=lval+rval+node.Val-1
res+=abs(tmp)
return tmp
}
dfs(root)
return res
}
func abs(i int)int{
if i>0{
return i
}
return -i
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.173 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716027389.A.611.html