1. 问题概述今天我们来讨论LeetCode第979题Distribute Coins in Binary Tree。这是一道关于二叉树和递归的经典问题考察我们对树结构的理解和递归算法的应用能力。问题的核心是给定一个二叉树的根节点其中每个节点的值代表该节点上的硬币数量。整个树的总硬币数等于树中的节点数即每个节点最终应该有且只有1个硬币。我们需要计算将硬币重新分配使得每个节点恰好有1个硬币所需的最少移动次数。每次移动硬币时我们可以选择将一枚硬币从一个节点移动到它的相邻节点父节点或子节点。2. 问题分析与解题思路2.1 理解题目要求首先我们需要明确几个关键点每个节点最终必须有且只有1个硬币硬币总数等于节点总数保证问题有解每次移动硬币只能沿着树的边进行父子节点之间需要计算最少的移动次数2.2 递归思路的建立这个问题非常适合使用递归来解决因为二叉树本身就是递归定义的数据结构每个子树的问题可以独立考虑父节点的解可以基于子节点的解构建我们可以考虑后序遍历左右根的方式因为我们需要先知道子树的硬币分布情况才能决定当前节点需要如何分配硬币。2.3 关键观察点对于任何一个节点它需要给予或接收的硬币数量等于它的硬币数与1的差值node-val - 1移动次数实际上等于硬币需要经过的边的数量每个节点的硬币平衡会影响其父节点的硬币平衡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 代码解析dfs函数如果节点为空返回0不需要也不提供硬币递归处理左子树和右子树得到它们各自需要给予/接收的硬币数移动次数增加abs(left) abs(right)硬币经过当前节点的移动次数返回当前节点及其子树总共需要给予/接收的硬币数root-val left right - 1distributeCoins函数初始化移动次数为0调用dfs函数处理整个树返回累计的移动次数3.3 时间复杂度分析这个算法的时间复杂度是O(N)其中N是树中的节点数。因为我们只是对每个节点进行一次访问没有重复计算。空间复杂度取决于树的形状最好情况平衡树O(logN)最坏情况退化为链表O(N)4. 示例解析4.1 简单示例考虑如下二叉树3 / \ 0 0初始状态根节点有3个硬币两个子节点各有0个硬币处理过程处理左子节点0需要1-01个硬币处理右子节点0需要1-01个硬币根节点3 (-1) (-1) - 1 0不需要给予父节点移动次数abs(-1) abs(-1) 24.2 复杂示例考虑如下二叉树0 / \ 3 0初始状态根节点有0个硬币左子节点有3个硬币右子节点有0个硬币处理过程处理左子节点3没有子节点返回3-12需要给予父节点2个硬币处理右子节点0没有子节点返回0-1-1需要从父节点接收1个硬币根节点0 2 (-1) - 1 0移动次数abs(2) abs(-1) 35. 常见问题与调试技巧5.1 常见错误忘记处理空节点递归函数中必须检查root NULL的情况移动次数计算错误应该在递归返回前累加移动次数而不是在其他位置返回值理解错误返回值表示当前子树需要给予/接收的硬币数不是移动次数5.2 调试技巧打印递归过程可以在递归函数中添加打印语句观察每个节点的处理顺序和返回值小规模测试先用手算小例子验证算法正确性边界测试测试单节点树、倾斜树等特殊情况5.3 优化思路虽然这个解法已经是最优的但可以考虑以下改进使用全局变量可能会被认为是不好的实践可以改为传递指针参数对于非常大的树可能需要考虑非递归的实现以避免栈溢出6. 算法扩展与变种6.1 类似问题二叉树的最大路径和同样使用后序遍历和递归思想二叉树的直径计算左右子树高度的和6.2 变种问题每个节点需要不同数量的硬币修改递归函数中的1为目标值移动硬币有不同成本根据移动方向或距离调整移动次数的计算方式N叉树的硬币分配将处理两个子节点扩展为处理多个子节点7. 个人实现心得在实际编码过程中我发现理解递归函数的返回值含义是最关键的一步。最初我尝试让递归函数直接返回移动次数这导致了计算错误。后来意识到应该让递归函数返回硬币的供需关系而在过程中累加移动次数问题就迎刃而解了。另一个重要的点是理解绝对值的必要性。因为无论是给予还是接收硬币都会产生移动次数所以需要使用abs()函数来计算。