在二叉树中分配硬币【LC979】
给定一个有
N个结点的二叉树的根结点root，树中的每个结点上都对应有node.val枚硬币，并且总共有N枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
好巧妙 没想出来
- 思路：
- 故该问题可以用树形dp解决，dfs返回每颗子树的金币数目和节点数目，计算每条边经过的金币数，累加返回结果
- 实现
class Solution { private int ans; public int distributeCoins(TreeNode root) { dfs(root); return ans; } private int[] dfs(TreeNode node) { if (node == null) return new int[]{0, 0}; var left = dfs(node.left); var right = dfs(node.right); int coins = left[0] + right[0] + node.val; // 子树硬币个数 int nodes = left[1] + right[1] + 1; // 子树节点数 ans += Math.abs(coins - nodes); return new int[]{coins, nodes}; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/distribute-coins-in-binary-tree/solutions/2343262/tu-jie-mei-you-si-lu-jin-lai-miao-dong-p-vrni/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { private int ans; public int distributeCoins(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node == null) return 0; int d = dfs(node.left) + dfs(node.right) + node.val - 1; ans += Math.abs(d); return d; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/distribute-coins-in-binary-tree/solutions/2343262/tu-jie-mei-you-si-lu-jin-lai-miao-dong-p-vrni/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
