LeetCode题解979. 在二叉树中分配硬币

给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。

在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。)。

返回使每个结点上只有一枚硬币所需的移动次数。

 

示例 1:

LeetCode题解979. 在二叉树中分配硬币

输入:[3,0,0]

输出:2

解释:从树的根结点开始,我们将一枚硬币移到它的左子结点上,一枚硬币移到它的右子结点上。

示例 2:

LeetCode题解979. 在二叉树中分配硬币

输入:[0,3,0]

输出:3

解释:从根结点的左子结点开始,我们将两枚硬币移到根结点上 [移动两次]。然后,我们把一枚硬币从根结点移到右子结点上。

示例 3:

LeetCode题解979. 在二叉树中分配硬币

输入:[1,0,2]

输出:2

示例 4:

LeetCode题解979. 在二叉树中分配硬币

输入:[1,0,0,null,3]

输出:4

 

提示:

1<= N <= 100

0 <= node.val <= N

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/distribute-coins-in-binary-tree

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解:# 【图解】DFS(Python3)

## 思路
我们定义函数`DFS(node)`,其功能在于计算以node为顶点的子树的需要多少硬币才平衡,正数表示我有多余,负数表示我需要别人给我硬币。

我们知道一颗子树要想平衡,那么其节点的node.val之和应该等于节点的总数,因此`以node为顶点的子树的需要多少硬币才平衡`就等价于`node.val + l + r - 1`,其中l是 `dfs(node.left)`, r是` dfs(node.right)
`。 而我们的目标是求解移动多少步,才能使得树的金币平衡。

如下图: 实际上,我们需要移动的步骤就是`abs(3) + abs(-1) + abs(2) + abs(-1) + abs(2) + abs(0)`也就是 8步。

其正确性也容易证明,比如子节点的4,那么其一定有3个需要运出去的,并且我们只能运到父节点,然后父节点再看要不要继续转运。节点为0表示我们需要有一个从父节点转运过来,如果父节点不够它再管父节点或者另一个子节点要。因此我们只需要计算一共管别人要了多少次就行了,这恰好就是图中连线上的数字之和。

LeetCode题解979. 在二叉树中分配硬币
(图来自: https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal)

## 代码
```python
class Solution:

def distributeCoins(self, root: TreeNode) -> int:
self.cnt = 0

def dfs(node):
if not node:
return 0
l = dfs(node.left)
r = dfs(node.right)
self.cnt += abs(l) + abs(r)

return node.val + l + r - 1
dfs(root)
return self.cnt

```

**复杂度分析**
- 时间复杂度:$O(N)$,其中N为节点的个数
- 空间复杂度:$O(H)$,其中H为树的深度

欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解

![](https://pic.leetcode-cn.com/89ef69abbf02a2957838499a96ce3fbb26830aae52e3ab90392e328c2670cddc-file_1581478989502)

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈

LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。

10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924

LeetCode题解微信红包

微信红包 如何分配 让每个人在数学期望上是一样的?在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。