LeetCode: 979. Distribute Coins in Binary Tree

题目¶

原题地址： https://leetcode.com/problems/distribute-coins-in-binary-tree/

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins and there are n coins total.

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 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.

Example 3:

Input: root = [1,0,2]
Output: 2

Example 4:

Input: root = [1,0,0,null,3]
Output: 4

Constraints:

• The number of nodes in the tree is n.
• 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of Node.val is n.

题目大意是，n 个节点的二叉树中总共包含 n 个金币，通过移动金币确保所有节点都有一个金币， 即所有节点均分金币，求要实现均分金币所需要移动的次数（最优次数）。

解法¶

从下往上均分硬币，计算实现每层子树符合均分所需要的移动次数：

• 每层的移动次数等于左子树剩余或需要的硬币数量 + 右子树剩余或需要的硬币数
• 节点硬币数 - 1 即为该节点多余或需要的硬币数， * 如果是多余的硬币数的话，它需要把多余的硬币移动相应次数分给别的节点 * 如果是需要的硬币数的话，它就需要别的节点移动相应次数来把硬币分给它 * 无论是哪种情况都需要移动相应的次数才能实现均分
• 节点实际多余或需要的硬币数等于它本身多余的硬币数 + 左右子树多余的硬币数 - 本身需要的硬币数 - 左右子数需要的硬币数。
• 硬币会从下往上流动，遇到需要硬币的节点就把硬币分给它一个， 遇到有多余硬币的节点就把多余的收集起来

这个思路的 Python 代码类似下面这样：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def distributeCoins(self, root):
        self._move = 0
        self._helper(root)

        return self._move


    def _helper(self, root):
        """从下往上遍历"""
        if root is None:
            return 0

        # 左子数多余的硬币数，为正则多余，为负则需要
        left_remain = self._helper(root.left)
        # 右子树多余的硬币数，为正则多余，为负则需要
        right_remain = self._helper(root.right)
        # root 多余的硬币数，为正则多余，为负则需要
        root_remain = root.val - 1

        # 从下往上移动到当前节点需要移动的次数，通过 abs 来实现不区分是需要硬币还是多余硬币数
        self._move += abs(left_remain) + abs(right_remain)

        # 移动到当前节点后，多余的硬币数，为正则多余，为负则需要
        return root_remain + left_remain + right_remain