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

2022-03-07 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

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

题意分析

一棵有 n 个节点的二叉树，每个节点上有 node.val 枚硬币，全树硬币总数恰好等于 n。一次移动可以把一枚硬币从某个节点挪到它的相邻节点（父或子）。问把每个节点都变成恰好 1 枚硬币，最少需要多少次移动。

「硬币总数恰好等于节点数」是题目送的关键前提：它保证目标状态一定可达，所以本题不是可行性判定，而是纯粹的代价计算。

第二个关键点是「一次移动只挪一枚硬币，只能走一条边」。这意味着如果要把 3 枚硬币从某处经过某条边送出去，就要计 3 次移动。换句话说，总移动次数 = 每条边上流过的硬币数量之和（按绝对值计，方向不影响次数）。这一步把「操作序列的最优化」转成了「每条边的流量统计」，是整道题的思维转折点。

第三，硬币可以双向流动，某条边上可能既有向上的需求又有向下的需求吗？不会——对一条边，两侧的净差额是确定的，最优方案下这条边上的流向唯一、流量等于净差额的绝对值。任何来回搬运都只会增加次数，所以最优解就等于各边净差额绝对值之和。这个下界同时也是可达的：只要按净差额一次性搬运即可。

约束里节点数不超过 100，node.val 在 [0, n] 之间，规模极小，$O(n)$ 的一次遍历绰绰有余，说明本题考的是建模而非效率。

边界方面：空树返回 0；node.val 可以是 0（这个节点需要索取一枚），也可以大于 1（需要送出）；根节点没有父边，它的净差额必然是 0（总数等于节点数），不会产生额外移动。

解法：后序 DFS（余额回传）

核心思路

先想暴力：把「移动一枚硬币」当成状态转移做搜索，状态是整棵树的硬币分布，状态空间随节点数指数爆炸，完全不可行。这条路走不通不是因为常数大，而是因为建模层次错了——不该在「操作序列」这一层思考。

换个层次：既然总移动次数等于每条边上流过的硬币数之和，那就逐条边去算流量。对任意一条连接节点 u 与其父亲的边，把树在这条边处剪开，u 所在的那棵子树里的硬币数记为 coins、节点数记为 nodes，那么这棵子树最终需要 nodes 枚硬币，现有 coins 枚，净差额 balance = coins - nodes：

balance > 0：子树多出 balance 枚，必须从这条边向上送出 balance 枚，这条边贡献 balance 次移动；

balance < 0：子树缺 |balance| 枚，必须从这条边向下取入，贡献 |balance| 次；

balance == 0：这条边一枚都不用过，贡献 0 次。

三种情况统一为「这条边贡献 |balance| 次移动」。于是答案就是所有边的 |balance| 之和，而边与「非根节点」一一对应，所以只需对每个节点算出它子树的余额即可。

余额天然可以自底向上递推：balance(node) = node.val + balance(left) + balance(right) - 1。含义是——本节点的硬币，加上左右子树上传/下取的净额，再扣掉本节点自己要留的那 1 枚，剩下的就是要通过父边流出的量（为负则表示要流入）。空节点的余额定义为 0，因为它既没有硬币也不需要硬币。

维持的不变量是：dfs(node) 的返回值恒等于「以 node 为根的子树的硬币数减去节点数」，与调用它的上层无关；而累加器 moves 在 dfs(node) 返回时，已经计入了该子树内部所有边的流量。遍历必须是后序——先拿到左右子树的余额，才能结算本节点与两个孩子之间那两条边，也才能算出本节点自己的余额。

结算的位置要精确：在 node 处累加的是 |balance(left)| + |balance(right)|，也就是 node 与它两个孩子之间的边。node 与它父亲之间的那条边不在这里结算，而是留给父亲处理。这样每条边恰好被结算一次，不重不漏；根节点没有父边，也正好不需要额外处理。

解题步骤

定义递归返回值的语义：dfs(node) 返回该子树的余额 coins - nodes。为什么先把语义钉死：后面每一行都只需检查「返回值是否符合这个语义」，转移式不会写歪。

递归基：node == null 返回 0。为什么是 0：空子树里 0 枚硬币、0 个节点，差额自然为 0；用 0 作单位元还能让上层的加法与绝对值统一处理，不必对「只有一个孩子」的节点做特判。

先递归左右子树：left = dfs(node.left)、right = dfs(node.right)。为什么必须先递归再结算：本节点两条子边的流量由孩子的余额决定，不先算孩子就无从下手；这也正是「后序」的含义。

结算两条子边：moves += |left| + |right|。为什么取绝对值：移动次数与流向无关，向上送 3 枚和向下取 3 枚都是 3 次。为什么在这里累加而不是在孩子那一层：一条边只能被结算一次，约定「由父节点结算与孩子相连的边」最简洁，且根节点天然没有父边。

返回本子树余额：node.val + left + right - 1。为什么减 1：本节点自己要留下恰好一枚，剩余部分才是要跨越父边的流量。为什么把孩子的余额直接加进来：孩子多出来的硬币已经流到本节点、缺的也已从本节点补走，这些量此刻就体现为本节点可支配的净额。

主函数返回累加器：所有边都结算完毕，moves 即为答案。注意用成员变量或闭包捕获来累加，是因为递归的返回值已经被余额占用了；也可以改成返回二元组，但那样代码更长。

以 root = [3,0,0]（根为 3，两个孩子都是 0）走一遍，预期答案 2。
dfs(左孩子 0)：它没有孩子，left = dfs(null) = 0、right = 0，moves += 0 + 0，返回 0 + 0 + 0 - 1 = -1。含义是这棵子树缺 1 枚，需要从父边取入 1 枚。
dfs(右孩子 0)：同理返回 -1。
dfs(根 3)：left = -1、right = -1，moves += |-1| + |-1| = 2。返回 3 + (-1) + (-1) - 1 = 0——根子树就是整棵树，余额必为 0，与「总数等于节点数」的前提吻合，可以当作自检。
返回 moves = 2：从根各拿一枚分给左右孩子，两次移动，正确。

再看 root = [0,3,0]（根为 0，左孩子 3，右孩子 0），预期答案 3。
dfs(左孩子 3)：返回 3 + 0 + 0 - 1 = 2，表示这棵子树多出 2 枚要往上送。
dfs(右孩子 0)：返回 -1。
dfs(根 0)：moves += |2| + |-1| = 3。返回 0 + 2 + (-1) - 1 = 0。
返回 3：左孩子先把 2 枚送到根（2 次），根再把 1 枚送给右孩子（1 次），合计 3 次，正确。注意这里 moves 的两部分分别对应两条边的流量，边 根—左 过了 2 枚、边 根—右 过了 1 枚，与实际操作完全对应。

代码实现

class Solution {
    private int moves = 0;

    public int distributeCoins(TreeNode root) {
        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(n)$。

空间复杂度：$O(h)$，h 为树高。凭什么：除了一个累加器没有开辟辅助结构，额外空间全部来自递归调用栈，栈深等于当前路径长度；平衡树时为 $O(\log n)$，退化成链时为 $O(n)$。

关键点总结

遇到「最少操作次数」而操作是局部搬运时，先别想搜索，而要问「总代价能不能拆成各条边的独立贡献」。本题把答案拆成每条边的流量之和，一步把指数级问题变成线性遍历。

树上的「每条边贡献一次」类统计，统一约定由父节点结算与孩子相连的边，可以做到不重不漏，且根节点无父边这件事会自动被处理。

递归返回值只能承载一种语义。这里返回值给了余额，累加答案就得另外用成员变量或闭包；想清楚「谁返回、谁累加」是树形 DP 的通用分工。

空节点返回 0 是「用单位元消灭特判」的又一例：单孩子节点、叶子节点、空树全部落进主逻辑，一个 if 都不用多写。

取绝对值对应「次数与方向无关」，这一步别漏——余额是有符号的，代价是无符号的，两者的转换点就在累加那一行。

面试视角：这题的分水岭是能否说出「答案 = 各边流量之和，边流量 = 子树余额的绝对值」。把这句话讲清楚，代码只有五行；讲不清楚就会陷在模拟搬运的死胡同里。写完后可以用「根节点返回值必为 0」当自检点主动说出来，面试官会认为你验证过模型。

易错点总结

错误写法：返回值忘记减 1，写成 node.val + left + right → 用例 [3,0,0] 中根返回 3、左右孩子各返回 0，moves 累加为 0，答案从 2 变成 0。

错误写法：累加时不取绝对值，写成 moves += left + right → 用例 [0,3,0] 中 2 + (-1) = 1，正负抵消，答案从 3 变成 1。

错误写法：把本节点与父节点的边也在本层结算，写成 moves += |node.val + left + right - 1| 之外还加了子边 → 用例 [3,0,0] 中每条边被算两次，答案从 2 变成 4。

错误写法：用先序遍历，在递归子树之前就结算 → 用例 [0,3,0] 中结算时还不知道孩子的余额，只能拿到未初始化的 0，答案变成 0。

错误写法：空节点返回 1 或 -1 → 用例 [1,null,1] 这类单孩子结构中，不存在的孩子被算成有余额，凭空产生移动次数。

错误写法：把 moves 声明为 dfs 的局部变量 → 用例任意输入下每层递归各自持有一份，回溯后全部丢失，最终返回 0。

错误写法：Go 里把 dfs 写成普通函数并用全局变量累加 → 用例多组测试连续调用时上一组的 moves 没清零，答案被累加放大；闭包捕获局部变量才能保证每次调用独立。

错误写法：把余额理解成「节点数减硬币数」，符号取反后又照抄返回式 → 用例 [0,3,0] 中 left 变成 -2，虽然绝对值不变，但父层的 node.val + left + right - 1 会算出错误的余额，答案错乱。

错误写法：先统计每棵子树的节点数和硬币数两个值再相减，但节点数统计漏了自身 → 用例 [3,0,0] 中左孩子被算成 0 个节点，余额变成 0，本该产生的移动被抹掉。

错误写法：试图模拟真实搬运过程，每次挪一枚硬币并计数 → 用例中节点数虽小仍能得到正确答案，但一旦硬币高度集中（如根节点持有全部 n 枚），模拟步数达 $O(n^2)$，且代码要处理搬运顺序，远比统计余额复杂。

错误写法：认为答案与硬币的具体分布无关、只与节点数有关 → 用例 [1,1,1] 答案是 0 而 [3,0,0] 答案是 2，两者节点数相同，说明必须逐边计算。

相似题目

题目	难度	考察点
124. 二叉树中的最大路径和	困难	同为「返回值给子树信息、答案另用变量累计」的分工，但要对负贡献做截断
543. 二叉树的直径	简单	返回深度、在节点处结算跨越路径，是这套分工模式最简单的入门题
337. 打家劫舍 III	中等	需要返回「选/不选」两个状态，考的是状态拆分而不是流量守恒
968. 监控二叉树	困难	后序回传三态并贪心决策，同样是自底向上，但决策发生在回溯时
1339. 分裂二叉树的最大乘积	中等	也需先算每棵子树的和再枚举断边，但目标是乘积最大而非搬运代价
110. 平衡二叉树	简单	后序回传高度并在父层判定，练的是返回值语义统一与提前剪枝
236. 二叉树的最近公共祖先	中等	同为后序信息回传，但回传的是布尔式的「是否包含目标」而非数值