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
}