题目描述
思路解析
一句话答案：LeetCode 979 在二叉树中分配硬币：用后序遍历让每个节点回传子树盈余=左+右+本节点值-1，经过一条边的搬运次数就是子树盈余的绝对值，顺路累加即最少移动数，时间 O(n)。
每个节点只留 1 枚，最少挪几次
给一棵二叉树 root，每个节点写着几枚硬币，全树硬币总数正好等于节点个数。每步只能在相邻父子间挪一枚，要让每个节点最后恰好剩 1 枚，问最少挪几次。题面例子 root=[3,0,0]：根 3 枚、两孩子各 0 枚，根的两枚各挪一枚给一个孩子，两步到位，答案 2。
多的匀给少的，为什么数不清步数
总数等于节点数、硬币刚好够分，像把多的匀给缺的就行。可硬币只能一枚一枚沿边挪，多硬币的节点接济远处缺硬币的，中间隔着好几条边、每条都得走一遍，哪枚走哪条路根本理不清。
别盯着硬币，盯着每条边要过几枚
先别盯每枚硬币的路线，改盯树上的每一条边。一棵子树和父亲之间只有唯一一条边：子树内多的每一枚只能从这条边送上去，缺的每一枚也只能从这条边补下来。所以经过这条边的硬币数，就是这棵子树多或少的枚数，这个量叫子树的盈余。
盈余为正要往上送、为负要往下补，方向相反，但这条边搬的次数都是盈余的绝对值。全树最少移动数就是每条边盈余绝对值之和。
递归每个节点返回盈余，顺路累加边数
某条边的盈余得靠它底下子树先算完才知道多还是少；于是先啃完左右孩子、拿到盈余才轮到自己结算，这种先子后父就是后序遍历。对每个节点，先递归拿到左盈余 left 和右盈余 right，正是两条边各要搬的枚数，取绝对值加进答案：ans += |left| + |right|。
接着这个节点把自己这支盈余往上交：left + right + 本节点硬币数 - 1，末尾的 -1 就是它自留的那 1 枚；空节点回传 0。根节点处理完，ans 就攒齐了所有边的搬运次数。
root=[3,0,0] 两条边各搬几枚
拿题面的 [3,0,0] 亲手走一遍。后序先钻到左孩子叶子：它没有孩子，left 和 right 都是 0，盈余 = 0 + 0 + 0 - 1 = -1，缺 1 枚，回传 -1。右孩子叶子一模一样，回传 -1。回到根：两条边盈余分别是 -1 和 -1，ans += |-1| + |-1| = 2。根再算自己盈余 = -1 + -1 + 3 - 1 = 0，整棵树盈余归零，硬币刚好够分。ans 停在 2，正是题面答案：根把多的两枚各挪一枚给一个孩子，两步收工。
换一棵比 [3,0,0] 深一点的树：根 0 枚，左孩子 3 枚、底下挂着 0 枚和 2 枚两片叶子，右孩子 0 枚。两片叶子盈余 -1 和 +1，各记 1 进 ans；左孩子合起来 -1 + 1 + 3 - 1 = 2，这 2 枚要穿过它到根这条中间边往上搬，其中一枚原在底下那片 2 枚叶子上。根再记 |2| + |-1| = 3，四条边 1、1、2、1 攒成 5。
复杂度，和三个把答案带偏的写法
只走一遍后序遍历，每个节点结算一次都是常数操作，时间 O(n)，n 是节点数；额外只有递归栈，深度压到树高，树匀称时约 log n 层、退化成一条链时压满 n 层，空间最坏 O(n)。
几处一写就岔：dfs 回传移动次数而非盈余，整条链跟着崩；累加忘取绝对值，缺硬币的边盈余是负数，会算成负的搬运次数；公式漏掉末尾 -1，等于没扣每个节点自留的那枚。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条主线：DFS 回传的是「子树盈余」，而每条边要搬几次，就是它底下子树盈余的绝对值，顺路累加就是答案。
准备 · 从根开始后序遍历：开局累计移动次数是 0。后序 DFS 从根出发，但根现在算不了，得先知道左右两棵子树各自盈余多少。所以先一路往左下钻，钻到最底下的叶子，再自底向上一个节点一个节点地结算。盯住右边的结算面板，每结算一条边，累计移动次数就涨一截。
下钻 · 进入根：递归进入根（紫色），它上面 0 枚硬币，但它还有孩子，左右子树盈余都还不知道，现在算不了，所以继续往下钻，先把左边那一整支彻底搞定。
下钻 · 进入左孩子：递归进入左孩子（紫色），它上面 3 枚硬币，但它还有孩子，左右子树盈余都还不知道，现在算不了，所以继续往下钻，先把左边那一整支彻底搞定。
下钻 · 到左下叶子：递归一路往下，走到左下叶子（紫色），它上面有 0 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
结算 · 左下叶子 盈余 -1：结算左下叶子：它一个节点要留 1 枚给自己，盈余 = 手里的 0 枚减去要留的 1 枚 = -1。盈余是负的，说明它缺 1 枚，得靠父亲补进来。节点变绿表示处理完。
记账 · 左下叶子 缺 1：左下叶子缺的这 1 枚先记在账上。它自己变不出硬币，只能等父亲沿着它们之间那条边搬下来。这次搬运的次数，等会儿在父亲那一步连同这条边一起结算。
下钻 · 到右下叶子：递归一路往下，走到右下叶子（紫色），它上面有 2 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
结算 · 右下叶子 盈余 +1：结算右下叶子：它一个节点要留 1 枚给自己，盈余 = 手里的 2 枚减去要留的 1 枚 = +1。盈余是正的，说明它多出 1 枚，要往父亲送出去。节点变绿表示处理完。
记账 · 右下叶子 多 1：右下叶子多出的这 1 枚也先记账。它要往父亲那边送，沿的就是它和父亲之间那条唯一的边。送几次，等会儿在父亲那一步连这条边一起结算。
回到左孩子 · 左右盈余齐了：左右两个孩子都结算完，回到左孩子。现在两边盈余齐了：左边 -1，右边 +1。先把连着这两个孩子的两条边各要搬几次算清楚，再算左孩子自己往上交多少。
边 · 左孩子 ↔ 左下叶子：左下叶子这一支盈余 -1，缺 1 枚，得从左孩子沿这条边搬 1 枚下去。经过这条边一共移动 1 次，累计移动次数涨到 1。
边 · 左孩子 ↔ 右下叶子：右下叶子这一支盈余 +1，多 1 枚，要沿这条边往左孩子搬 1 枚上来。这条边移动 1 次，累计移动次数涨到 2。
上交 · 左孩子 盈余 +2：左孩子自己结算：左盈余 -1 加右盈余 +1 加自己 3 枚、再减去留给自己的 1 枚，盈余 = +2。它往上交给父亲的就是这个 +2，代表它这一整支净多 2 枚要继续往上送。节点变绿。
下钻 · 到右孩子：递归一路往下，走到右孩子（紫色），它上面有 0 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
结算 · 右孩子 盈余 -1：结算右孩子：它一个节点要留 1 枚给自己，盈余 = 手里的 0 枚减去要留的 1 枚 = -1。盈余是负的，说明它缺 1 枚，得靠父亲补进来。节点变绿表示处理完。
记账 · 右孩子 缺 1：右孩子缺的这 1 枚先记在账上。它自己变不出硬币，只能等父亲沿着它们之间那条边搬下来。这次搬运的次数，等会儿在父亲那一步连同这条边一起结算。
回到根 · 左右盈余齐了：左右两个孩子都结算完，回到根。现在两边盈余齐了：左边 +2，右边 -1。先把连着这两个孩子的两条边各要搬几次算清楚，再算根自己往上交多少。
边 · 根 ↔ 左孩子：左孩子这一支盈余 +2，多 2 枚，要沿这条边往根搬 2 枚上来。经过这条边一共移动 2 次，累计移动次数涨到 4。
边 · 根 ↔ 右孩子：右孩子这一支盈余 -1，缺 1 枚，得从根沿这条边搬 1 枚下去。这条边移动 1 次，累计移动次数涨到 5。
结算根 · 全树盈余 0：轮到根结算：左边盈余 +2、右边盈余 -1，加根自己的 0 枚、再减去它要留的 1 枚，盈余 = 0。整棵树盈余正好归零，说明硬币不多不少刚够分，符合题目「总数等于节点数」的前提。根变绿，所有边都结算完了。
回放 · 硬币怎么流动：回放一下硬币的流向：左下叶子缺的 1 枚，从左孩子搬下来，1 次；右下叶子多的 1 枚，交给左孩子，1 次；左孩子这一支算下来净多 2 枚，全搬到根上，2 次；根再把 1 枚搬给缺钱的右孩子，1 次。四条边分别是 1、1、2、1。
完成 · 累计就是答案：把四条边的移动次数加起来：1 加 1 加 2 加 1，正好等于 5，这就是让每个节点都恰好剩 1 枚硬币的最少移动次数。整个过程只走了一遍后序遍历，盈余一路往上递、移动次数顺路累加，一次搞定，时间是 O(n)。
边界先想清：单节点和全 1 的树都不用搬；只要有节点多或少，对应的边就要搬 |盈余| 次。
面试核心：解释清「一条边、唯一通道，盈余的绝对值就是搬运次数」这个直觉。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: def dfs(root): if root is None: return 0 left, right = dfs(root.left), dfs(root.right) nonlocal ans ans += abs(left) + abs(right) return left + right + root.val - 1 ans = 0 dfs(root) return ans复杂度
- 时间：O(n)，后序遍历每个节点只访问、结算一次，算盈余和累加边移动都是常数操作
- 空间：O(h)，只用递归栈，深度等于树高 h；最坏（链状树）退化到 O(n)，平衡树是 O(log n)
易错点
面试追问把动画讲成自己的话
追问为什么经过一条边的移动次数，正好等于它下面子树盈余的绝对值？
追问盈余为负到底代表什么方向的移动？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从叶结点开始的最小字符串
LeetCode 988 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题