https://leetcode.cn/problems/distribute-coins-in-binary-tree/
这个题刚开始的思路是对树进行一个中序遍历，像有一个铲子从左往右推，所过之处摞起来的金币堆都被铲平，多出来的金币落到右边的金币坑里（或左边的金币坑）
但是这样有一个问题，怎么知道多余的金币是从哪个位置来的呢，那岂不是每个金币都要存它是谁多出来的，然后再算从当前位置到原始位置的距离，太繁琐了
既然这样不行，考虑分治，每一个子树都相当于进行了一个调度，把左边多出来的放到右边，右边多出来的放到左边
这个过程金币不一定够，父亲还得向上借。不过这个不用担心，先假装借到了，因为肯定够
父亲要借的金币数刚好也是爷爷所要知道的调度的信息，就以这个作为dfs传递的值吧
但是写着写着发现，光有这个量还不够，我们要最终求的是调度的步数，光是传递金币的量不行，还要传递步数
对于一个子树，要做的有三个步骤：左孩子平衡好自身，有孩子平衡好自身，向上借/供奉金币
向上借/供奉金币所做的步数，正好就是刚才的那个金币数
平衡好自身需要的步骤数=左孩子平衡步骤数+右孩子平衡步骤数+向上借/供奉金币数
因此，步骤数也应作为dfs传递的量
看了题解，有人是后序遍历（仔细想想，我这个虽然函数名写的dfs，也应该归到后序遍历上，因为虽然搜索的过程是根左右，但是处理的顺序是左右根，先搜到了根，但是等左右处理好了才根据它们的值再处理根），然后她也递归，但是只传一个值
private int ans = 0;
public int lrd(TreeNode root){
root.val += lrd(root.left);
root.val += lrd(root.right);
ans += Math.abs(root.val - 1);
return root.val - 1;
}
她直接把.val给改了，相当于改成了我那里的借/多的金币，这样就不用传了
步数那块，她没有管左边平衡自己要多少步，右孩子平衡自身要多少步，它只关心一个数据，那就是要向上借/送多少个金币。这是自己比孩子多做的事
而孩子要多少步，孩子自己会直接告诉全局变量ans的。反正每个节点都只处理一次，不重不漏的文章来源：https://www.toymoban.com/news/detail-560926.html
这样挺好，这才是真正的分治，管好自己，管孩子干啥文章来源地址https://www.toymoban.com/news/detail-560926.html
到了这里，关于【算法心得】硬币通过二叉树传递的题，分治精髓是干自己的事的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
