介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

(相关资料图)

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

在二叉树中分配硬币

题目看这里，leetcode第979题，hard难度：/problems/distribute-coins-in-binary-tree/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

久违的难题！首先的observation是，可以用一个变量表示当前树需要多少硬币/能给出多少硬币。这里我们左右两边先分别计算出这个值。比如说左边树要5个硬币，右边要-3个。那么此时根节点的硬币数应该是多少？有聪明的同学可以得出，5-3+1 = 3。+1是因为根节点也需要一个硬币。如果根节点的硬币数不够或者有余，那么就把这个值上报给更上一级的节点，这是个递归的过程。

在这个过程中，每层我们都会以根节点为连接，把硬币从左右子树之间移动。最小的移动次数即为积累的移动次数的和。

思考乐园

计算移动次数的时候，为什么用了abs函数？欢迎将答案写在评论区～

音乐推荐

究竟是要做的事情太多导致博得之门变得好玩，还是已经焦头烂额的我没有兴趣去玩博得之门，这是一个很好的问题。今天要推荐的歌曲是来自輕鸞軸心的我爱你就像拖拉机下山叮铃哐当叮铃，不知道为什么是ktv版本的，送给两眼一黑的你。

教材链接

【1】/blog/leetcode-problem-categories/