java 解法, 执行用时: 0 ms, 内存消耗: 39.7 MB, 提交时间: 2023-07-14 09:14:13

/**
 * 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 int ans = 0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return this.ans;
    }
    
    private int dfs(TreeNode node) {
        if ( node == null ) {
            return 0;
        }
        int L = dfs(node.left);
        int R = dfs(node.right);
        this.ans += Math.abs(L) + Math.abs(R);
        return node.val + L + R - 1;
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 3.1 MB, 提交时间: 2022-11-17 11:39:50

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distributeCoins(root *TreeNode) int {
    ans := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        L, R := dfs(node.Left), dfs(node.Right)
        ans += abs(L) + abs(R)        
        return node.Val + L + R - 1
    }
    dfs(root)
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

python3 解法, 执行用时: 44 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-17 11:34:24

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

'''
如果树的叶子仅包含 0 枚金币（与它所需相比，它的 过载量 为 -1），那么我们需要从它的父亲节点移动一枚金币到这个叶子节点上。
如果说，一个叶子节点包含 4 枚金币（它的 过载量 为 3），那么我们需要将这个叶子节点中的 3 枚金币移动到别的地方去。
总的来说，对于一个叶子节点，需要移动到它中或需要从它移动到它的父亲中的金币数量为 过载量 = Math.abs(num_coins - 1)。
然后，在接下来的计算中，我们就再也不需要考虑这些已经考虑过的叶子节点了。

我们可以用上述的方法来逐步构建我们的最终答案。
定义 dfs(node) 为这个节点所在的子树中金币的 过载量，也就是这个子树中金币的数量减去这个子树中节点的数量。
接着，我们可以计算出这个节点与它的子节点之间需要移动金币的数量为 abs(dfs(node.left)) + abs(dfs(node.right))，
这个节点金币的过载量为 node.val + dfs(node.left) + dfs(node.right) - 1。
'''
class Solution(object):
    def distributeCoins(self, root):
        self.ans = 0

        def dfs(node):
            if not node: return 0
            L, R = dfs(node.left), dfs(node.right)
            self.ans += abs(L) + abs(R)
            return node.val + L + R - 1

        dfs(root)
        return self.ans