0979. Distribute Coins in Binary Tree¶
题目信息¶
- 题号:
0979
- 难度:
Medium
- 主题:
二叉树、硬币流动、最少边移动
- 原题:
- 重点:
树有
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
解释:唯一节点已经满足恰有一枚硬币,不需要沿边移动。