#979

Distribute Coins in Binary Tree

pupil · 465 · lc medium +26 · verified · 77.3% accepted · 6,064 likes · top 88%

Description

The binary tree root has n nodes collectively holding n coins (not necessarily one per node). Each move transfers one coin across an adjacent edge. Return the minimum moves required so every node ends up with 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.

Code

# 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 = right
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:

# 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 = right
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int: