Medium

题目描述

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整个树上一共有 n 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点到父结点。

返回使每个结点都恰好有一枚硬币所需的最少移动次数。

示例 1：

输入：root = [3,0,0]
输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。

示例 2：

输入：root = [0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上（花费两次移动）。然后，我们把一枚硬币从根结点移到右子结点上。

提示：

  • 树中节点的数目为 n
  • 1 <= n <= 100
  • 0 <= Node.val <= n
  • 所有 Node.val 的值之和为 n

解题思路

这道题的关键insight是：对于任意一个子树，我们只需要知道它需要从外部获取多少硬币，或者能向外部提供多少硬币。

核心思路是使用DFS进行后序遍历，计算每个节点的"净需求"。对于每个节点：

  • 如果子树总硬币数 > 子树节点数，说明子树有多余硬币，需要向上传递
  • 如果子树总硬币数 < 子树节点数，说明子树缺少硬币，需要从上获取

具体算法步骤：

  1. 对每个节点，先递归处理左右子树
  2. 计算当前子树的净需求：(左子树净需求) + (右子树净需求) + (当前节点硬币数) - 1
  3. 移动次数累加绝对值：|左子树净需求| + |右子树净需求|

这里的关键理解是：净需求为正表示子树有多余硬币要向上传递，为负表示子树缺硬币需要从上获取。无论哪种情况，都需要通过父子间的边进行传递，所以移动次数就是净需求的绝对值。

时间复杂度O(n)，空间复杂度O(h)，其中h是树的高度。

代码实现

class Solution {
public:
    int moves = 0;
    
    int dfs(TreeNode* node) {
        if (!node) return 0;
        
        int left_excess = dfs(node->left);
        int right_excess = dfs(node->right);
        
        moves += abs(left_excess) + abs(right_excess);
        
        return node->val + left_excess + right_excess - 1;
    }
    
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return moves;
    }
};

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_excess = dfs(node.left)
            right_excess = dfs(node.right)
            
            self.moves += abs(left_excess) + abs(right_excess)
            
            return node.val + left_excess + right_excess - 1
        
        dfs(root)
        return self.moves

public class Solution {
    private int moves = 0;
    
    private int Dfs(TreeNode node) {
        if (node == null) return 0;
        
        int leftExcess = Dfs(node.left);
        int rightExcess = Dfs(node.right);
        
        moves += Math.Abs(leftExcess) + Math.Abs(rightExcess);
        
        return node.val + leftExcess + rightExcess - 1;
    }
    
    public int DistributeCoins(TreeNode root) {
        moves = 0;
        Dfs(root);
        return moves;
    }
}

var distributeCoins = function(root) {
    let moves = 0;
    
    function dfs(node) {
        if (!node) return 0;
        
        const leftExcess = dfs(node.left);
        const rightExcess = dfs(node.right);
        
        moves += Math.abs(leftExcess) + Math.abs(rightExcess);
        
        return node.val + leftExcess + rightExcess - 1;
    }
    
    dfs(root);
    return moves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(n)
空间复杂度O(h)

其中 n 是树中节点的数量，h 是树的高度。时间复杂度为 O(n) 因为需要遍历每个节点一次；空间复杂度为 O(h) 主要来自递归调用栈的深度。

相关题目