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
}