1. 问题概述

今天我们来讨论LeetCode第979题"Distribute Coins in Binary Tree"。这是一道关于二叉树和递归的经典问题，考察我们对树结构的理解和递归算法的应用能力。

问题的核心是：给定一个二叉树的根节点，其中每个节点的值代表该节点上的硬币数量。整个树的总硬币数等于树中的节点数（即每个节点最终应该有且只有1个硬币）。我们需要计算将硬币重新分配，使得每个节点恰好有1个硬币所需的最少移动次数。每次移动硬币时，我们可以选择将一枚硬币从一个节点移动到它的相邻节点（父节点或子节点）。

2. 问题分析与解题思路

2.1 理解题目要求

首先，我们需要明确几个关键点：

1. 每个节点最终必须有且只有1个硬币
2. 硬币总数等于节点总数（保证问题有解）
3. 每次移动硬币只能沿着树的边进行（父子节点之间）
4. 需要计算最少的移动次数

2.2 递归思路的建立

这个问题非常适合使用递归来解决，因为：

1. 二叉树本身就是递归定义的数据结构
2. 每个子树的问题可以独立考虑
3. 父节点的解可以基于子节点的解构建

我们可以考虑后序遍历（左右根）的方式，因为我们需要先知道子树的硬币分布情况，才能决定当前节点需要如何分配硬币。

2.3 关键观察点

1. 对于任何一个节点，它需要"给予"或"接收"的硬币数量等于它的硬币数与1的差值（node->val - 1）
2. 移动次数实际上等于硬币需要"经过"的边的数量
3. 每个节点的硬币平衡会影响其父节点的硬币平衡

3. 算法设计与实现

3.1 递归函数设计

我们定义一个递归函数dfs，它返回当前子树需要"给予"或"接收"的硬币数量（正数表示需要给予父节点，负数表示需要从父节点接收）。同时，我们在递归过程中累加移动次数。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int moves; int dfs(struct TreeNode* root) { if (!root) return 0; int left = dfs(root->left); int right = dfs(root->right); moves += abs(left) + abs(right); return root->val + left + right - 1; } int distributeCoins(struct TreeNode* root) { moves = 0; dfs(root); return moves; }

3.2 代码解析

1. dfs函数：

   • 如果节点为空，返回0（不需要也不提供硬币）
   • 递归处理左子树和右子树，得到它们各自需要给予/接收的硬币数
   • 移动次数增加abs(left) + abs(right)（硬币经过当前节点的移动次数）
   • 返回当前节点及其子树总共需要给予/接收的硬币数（root->val + left + right - 1）

2. distributeCoins函数：

   • 初始化移动次数为0
   • 调用dfs函数处理整个树
   • 返回累计的移动次数

3.3 时间复杂度分析

这个算法的时间复杂度是O(N)，其中N是树中的节点数。因为我们只是对每个节点进行一次访问，没有重复计算。

空间复杂度取决于树的形状：

• 最好情况（平衡树）：O(logN)
• 最坏情况（退化为链表）：O(N)

4. 示例解析

4.1 简单示例

考虑如下二叉树：

3 / \ 0 0

初始状态：

• 根节点有3个硬币
• 两个子节点各有0个硬币

处理过程：

1. 处理左子节点（0）：需要1-0=1个硬币
2. 处理右子节点（0）：需要1-0=1个硬币
3. 根节点：3 + (-1) + (-1) - 1 = 0（不需要给予父节点）
4. 移动次数：abs(-1) + abs(-1) = 2

4.2 复杂示例

考虑如下二叉树：

0 / \ 3 0

初始状态：

• 根节点有0个硬币
• 左子节点有3个硬币
• 右子节点有0个硬币

处理过程：

1. 处理左子节点（3）：
   • 没有子节点，返回3-1=2（需要给予父节点2个硬币）
2. 处理右子节点（0）：
   • 没有子节点，返回0-1=-1（需要从父节点接收1个硬币）
3. 根节点：0 + 2 + (-1) - 1 = 0
4. 移动次数：abs(2) + abs(-1) = 3

5. 常见问题与调试技巧

5.1 常见错误

1. 忘记处理空节点：递归函数中必须检查root == NULL的情况
2. 移动次数计算错误：应该在递归返回前累加移动次数，而不是在其他位置
3. 返回值理解错误：返回值表示当前子树需要给予/接收的硬币数，不是移动次数

5.2 调试技巧

1. 打印递归过程：可以在递归函数中添加打印语句，观察每个节点的处理顺序和返回值
2. 小规模测试：先用手算小例子验证算法正确性
3. 边界测试：测试单节点树、倾斜树等特殊情况

5.3 优化思路

虽然这个解法已经是最优的，但可以考虑以下改进：

1. 使用全局变量可能会被认为是不好的实践，可以改为传递指针参数
2. 对于非常大的树，可能需要考虑非递归的实现以避免栈溢出

6. 算法扩展与变种

6.1 类似问题

1. 二叉树的最大路径和：同样使用后序遍历和递归思想
2. 二叉树的直径：计算左右子树高度的和

6.2 变种问题

1. 每个节点需要不同数量的硬币：修改递归函数中的"1"为目标值
2. 移动硬币有不同成本：根据移动方向或距离调整移动次数的计算方式
3. N叉树的硬币分配：将处理两个子节点扩展为处理多个子节点

7. 个人实现心得

在实际编码过程中，我发现理解递归函数的返回值含义是最关键的一步。最初我尝试让递归函数直接返回移动次数，这导致了计算错误。后来意识到应该让递归函数返回硬币的供需关系，而在过程中累加移动次数，问题就迎刃而解了。

另一个重要的点是理解绝对值的必要性。因为无论是给予还是接收硬币，都会产生移动次数，所以需要使用abs()函数来计算。