LeetCode 979. 在二叉树中分配硬币

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
深度优先搜索 树 二叉树

题目描述

✅ 979. 在二叉树中分配硬币

image-20260929105448381

image-20260929105448643

题意分析

树的硬币总数恰好等于节点数。每次可以沿一条父子边移动一枚硬币，方向不限，要求最终每个节点恰好一枚，并让总移动次数最少。一个硬币经过多条边，需要为经过的每条边各计一次移动。

解法：后序递归统计子树余额

核心思路

[!blue]

考虑一棵子树，它与外部只有连接父节点的这一条边。定义余额为“子树硬币总数减去节点数”：余额为正，多出的硬币必须流出；余额为负，缺少的硬币必须从外部流入。因此这条父边至少需要发生 abs(余额) 次移动，任何安排都绕不开这个下界。

用 dfs(node) 返回当前子树余额。先递归得到左右子树的 left、right，再加上当前节点自己的硬币 node.val，并为自身保留一枚，得到 node.val + left + right - 1。空子树没有硬币也没有需求，余额为 0。

当前节点负责结算它与两个孩子相连的边，将 abs(left) + abs(right) 加入 moves。孩子内部的边已在递归中结算，因此每条真实边恰好计算一次；正负余额表示方向，计算次数时不能互相抵消。

这些边上的下界可以同时达到：先自底向上汇出各子树的净盈余，再自顶向下补足净缺口，每条边只按净需求的方向传递相应数量，不需要来回搬运。全树总量平衡，根的余额为 0，所以没有额外硬币需要流向树外，所有节点最终都能保留一枚。故累加每条边的绝对余额就是最少移动次数。

解题步骤

  1. 每次公开调用先将累计移动次数清零。
  2. 递归遇到空节点时返回余额 0。
  3. 后序遍历，先取得左右子树余额，再把它们的绝对值加入总移动次数。
  4. 返回当前节点硬币加上两侧余额、再减去自身一枚需求后的结果。
  5. 根递归完成后，返回累计的 moves，而不是根的余额。

代码实现

class Solution {
    private int moves = 0;

    public int distributeCoins(TreeNode root) {
        // 每次调用重新计数，避免前一棵树的结果残留。
        moves = 0;
        dfs(root);

        return moves;
    }

    // 返回该子树的余额：硬币数 - 节点数，正数表示要向上送出。
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        // 结算当前节点与两个孩子之间的边，流量即余额的绝对值。
        moves += Math.abs(left) + Math.abs(right);

        return node.val + left + right - 1;
    }
}

func distributeCoins(root *TreeNode) int {
    moves := 0

    // 返回该子树的余额：硬币数 - 节点数，正数表示要向上送出。
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := dfs(node.Left)
        right := dfs(node.Right)
        // 结算当前节点与两个孩子之间的边，流量即余额的绝对值。
        moves += abs(left) + abs(right)
        return node.Val + left + right - 1
    }

    dfs(root)
    return moves
}

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

复杂度分析

  • 时间复杂度：$O(n)$，每个节点访问一次，每条父子边结算一次。
  • 空间复杂度：$O(h)$，递归深度由树高 $h$ 决定；树退化成链时最坏为 $O(n)$。

关键点总结

[!green]

  • 子树只有一条通向外部的边，供需差直接确定这条边必须承担的净流量。
  • 返回值是有正负的余额，全局累加的是非负移动次数，两者不能混用。
  • 每条边的必要流量下界可以同时实现，因此求和得到最优答案。

易错点总结

[!yellow]

  • 返回余额时忘记减去当前节点所需的一枚，会错误计算整个子树的供需。
  • 把正负余额直接相加作为移动数，会抵消不同边上本来都必须发生的移动。
  • 在父节点和子节点处重复结算同一条边，会多算次数。
  • 根的余额应为 0，但不代表无需移动；答案是各边已经累计的流量。
  • Java 累加器是成员字段，每次公开调用都要重置，避免混入上一棵树的结果。

相似题目

题目 难度 关联与区别
517. 超级洗衣机 困难 同样用子结构盈亏计算必须跨边移动的数量，本题统计总移动次数，洗衣机题还限制并行传递轮次。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/27044255
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！