Problem: 979. 在二叉树中分配硬币

思路

这道题目要求我们计算在给定的二叉树中，移动硬币使每个节点恰好有一个硬币所需的最小步数。每个节点的值表示该节点上的硬币数量，而我们的目标是通过移动硬币使得每个节点都恰好有1个硬币。

解题方法

定义一个内部类Info来存储每个子树的节点数量（cnts）、硬币数量（sum）和移动硬币的步数（moves）。然后，从根节点开始，使用递归函数f遍历整棵树，对于每一个节点，我们先递归处理其左右子树，得到子树的相关信息。之后，根据子树的节点数和硬币数，我们可以计算出当前节点处硬币的盈余或短缺情况，并将其转换为移动步数的一部分。最后返回整个树的总移动步数。

复杂度

时间复杂度:

$O(n)$，其中nn是二叉树中的节点数。因为我们需要访问树中的每个节点一次。

空间复杂度:

$O(h)$，其中hh是二叉树的高度。这是由于递归过程中栈的深度取决于树的高度。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public class Info{
        public int cnts;
        public int sum;
        public int moves;
        public Info(int cnts, int sum, int moves) {
            this.cnts = cnts;
            this.sum = sum;
            this.moves = moves;
        }
    }
    public int distributeCoins(TreeNode root) {
        return f(root).moves;
    }
    public Info f(TreeNode x) {
        if(x == null) {
            return new Info(0, 0, 0);
        }
        Info infol = f(x.left);
        Info infor = f(x.right);
        int cnts = infol.cnts + infor.cnts + 1;
        int sum = infol.sum + infor.sum + x.val;
        int moves = infol.moves + infor.moves + Math.abs(infol.cnts - infol.sum) + Math.abs(infor.cnts - infor.sum);
        return new Info(cnts, sum, moves);

    }
}