在二叉树中分配硬币 图解题解

这道题到底在问什么

输入

root=[3,0,0]

输出

2（根上 3 枚，分别挪 1 枚给左孩子、1 枚给右孩子）

最优解：一步一步想明白

1. 3记住这条主线：DFS 回传的是「子树盈余」，而每条边要搬几次，就是它底下子树盈余的绝对值，顺路累加就是答案。
2. 4栈空，累计移动 0开局累计移动次数是 0。后序 DFS 从根出发，但根现在算不了，得先知道左右两棵子树各自盈余多少。所以先一路往左下钻，钻到最底下的叶子，再自底向上一个节点一个节点地结算。盯住右边的结算面板，每结算一条边，累计移动次数就涨一截。
3. 5进入根（0枚）递归进入根（紫色），它上面 0 枚硬币，但它还有孩子，左右子树盈余都还不知道，现在算不了，所以继续往下钻，先把左边那一整支彻底搞定。
4. 6进入左孩子（3枚）递归进入左孩子（紫色），它上面 3 枚硬币，但它还有孩子，左右子树盈余都还不知道，现在算不了，所以继续往下钻，先把左边那一整支彻底搞定。
5. 7看左下叶子（0枚）递归一路往下，走到左下叶子（紫色），它上面有 0 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
6. 8盈余 = 0-1 = -1结算左下叶子：它一个节点要留 1 枚给自己，盈余 = 手里的 0 枚减去要留的 1 枚 = -1。盈余是负的，说明它缺 1 枚，得靠父亲补进来。节点变绿表示处理完。
7. 9缺 1 枚待补左下叶子缺的这 1 枚先记在账上。它自己变不出硬币，只能等父亲沿着它们之间那条边搬下来。这次搬运的次数，等会儿在父亲那一步连同这条边一起结算。
8. 10看右下叶子（2枚）递归一路往下，走到右下叶子（紫色），它上面有 2 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
9. 11盈余 = 2-1 = +1结算右下叶子：它一个节点要留 1 枚给自己，盈余 = 手里的 2 枚减去要留的 1 枚 = +1。盈余是正的，说明它多出 1 枚，要往父亲送出去。节点变绿表示处理完。
10. 12多 1 枚待送右下叶子多出的这 1 枚也先记账。它要往父亲那边送，沿的就是它和父亲之间那条唯一的边。送几次，等会儿在父亲那一步连这条边一起结算。
11. 13左 -1 · 右 +1左右两个孩子都结算完，回到左孩子。现在两边盈余齐了：左边 -1，右边 +1。先把连着这两个孩子的两条边各要搬几次算清楚，再算左孩子自己往上交多少。
12. 14|-1| = 1 次 · 累计 1左下叶子这一支盈余 -1，缺 1 枚，得从左孩子沿这条边搬 1 枚下去。经过这条边一共移动 1 次，累计移动次数涨到 1。
13. 15|+1| = 1 次 · 累计 2右下叶子这一支盈余 +1，多 1 枚，要沿这条边往左孩子搬 1 枚上来。这条边移动 1 次，累计移动次数涨到 2。
14. 16盈余 = -1+1+3-1 = +2左孩子自己结算：左盈余 -1 加右盈余 +1 加自己 3 枚、再减去留给自己的 1 枚，盈余 = +2。它往上交给父亲的就是这个 +2，代表它这一整支净多 2 枚要继续往上送。节点变绿。
15. 17看右孩子（0枚）递归一路往下，走到右孩子（紫色），它上面有 0 枚硬币，没有孩子，是个叶子。叶子左右都是空，下一帧直接结算它的盈余。
16. 18盈余 = 0-1 = -1结算右孩子：它一个节点要留 1 枚给自己，盈余 = 手里的 0 枚减去要留的 1 枚 = -1。盈余是负的，说明它缺 1 枚，得靠父亲补进来。节点变绿表示处理完。
17. 19缺 1 枚待补右孩子缺的这 1 枚先记在账上。它自己变不出硬币，只能等父亲沿着它们之间那条边搬下来。这次搬运的次数，等会儿在父亲那一步连同这条边一起结算。
18. 20左 +2 · 右 -1左右两个孩子都结算完，回到根。现在两边盈余齐了：左边 +2，右边 -1。先把连着这两个孩子的两条边各要搬几次算清楚，再算根自己往上交多少。
19. 21|+2| = 2 次 · 累计 4左孩子这一支盈余 +2，多 2 枚，要沿这条边往根搬 2 枚上来。经过这条边一共移动 2 次，累计移动次数涨到 4。
20. 22|-1| = 1 次 · 累计 5右孩子这一支盈余 -1，缺 1 枚，得从根沿这条边搬 1 枚下去。这条边移动 1 次，累计移动次数涨到 5。
21. 23盈余 = +2-1+0-1 = 0轮到根结算：左边盈余 +2、右边盈余 -1，加根自己的 0 枚、再减去它要留的 1 枚，盈余 = 0。整棵树盈余正好归零，说明硬币不多不少刚够分，符合题目「总数等于节点数」的前提。根变绿，所有边都结算完了。
22. 241 + 1 + 2 + 1回放一下硬币的流向：左下叶子缺的 1 枚，从左孩子搬下来，1 次；右下叶子多的 1 枚，交给左孩子，1 次；左孩子这一支算下来净多 2 枚，全搬到根上，2 次；根再把 1 枚搬给缺钱的右孩子，1 次。四条边分别是 1、1、2、1。
23. 25答案 = 5把四条边的移动次数加起来：1 加 1 加 2 加 1，正好等于 5，这就是让每个节点都恰好剩 1 枚硬币的最少移动次数。整个过程只走了一遍后序遍历，盈余一路往上递、移动次数顺路累加，一次搞定，时间是 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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 = right
class 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 = right
class 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int distributeCoins(TreeNode* root) {
        int ans = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* root) -> int {
            if (!root) {
                return 0;
            }
            int left = dfs(root->left);
            int right = dfs(root->right);
            ans += abs(left) + abs(right);
            return left + right + root->val - 1;
        };
        dfs(root);
        return ans;
    }
};

import java.util.*;
/**
 * 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 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int ans;

    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        ans += Math.abs(left) + Math.abs(right);
        return left + right + root.val - 1;
    }
}

复杂度

面试官可能追问