题目描述
思路解析动画文字版
记住这条主线：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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题