You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
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.
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516171819
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defdistributeCoins(self,root:Optional[TreeNode])->int:defdfs(root):ifrootisNone:return0left,right=dfs(root.left),dfs(root.right)nonlocalansans+=abs(left)+abs(right)returnleft+right+root.val-1ans=0dfs(root)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcdistributeCoins(root*TreeNode)(ansint){vardfsfunc(*TreeNode)intdfs=func(root*TreeNode)int{ifroot==nil{return0}left,right:=dfs(root.Left),dfs(root.Right)ans+=abs(left)+abs(right)returnleft+right+root.Val-1}dfs(root)return}funcabs(xint)int{ifx<0{return-x}returnx}