0979. Distribute Coins in Binary Tree

题目信息

题号:

0979

难度:

Medium

主题:

二叉树、硬币流动、最少边移动

原题:

LeetCode 0979

重点:

树有 n 个节点且总硬币数恰为 n;一次只能沿父子边移动一枚硬币,目标是让每个节点恰有一枚并最小化移动次数

题目重述

给定一棵有 n 个节点的二叉树,节点值表示该节点当前拥有的硬币数。整棵树中的硬币总数恰好为 n。

一次操作可以选择一对直接相邻的父子节点,把一枚硬币从其中一个节点移动到另一个节点,方向不限。请返回使每个节点最终都恰好拥有一枚硬币所需的最少操作次数。

1 <= n <= 100,0 <= node.val <= n,所有节点值之和为 n。

自建示例

多余硬币需要跨过根节点:

输入:root = [0,0,4,null,null,0]
输出:4
解释:值为 4 的右孩子给自己的左孩子一枚硬币需要 1 次;向根节点输送两枚需要 2 次,其中一枚再由根移动到左孩子需要 1 次,总计 4。

单节点已经拥有一枚硬币:

输入:root = [1]
输出:0
解释:唯一节点已经满足恰有一枚硬币,不需要沿边移动。