在二叉树中分配硬币
难度:
标签:
题目描述
给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。
返回使每个结点上 只有 一枚硬币所需的 最少 移动次数。
示例 1：
输入：root = [3,0,0] 输出：2 解释：一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。
示例 2：
输入：root = [0,3,0] 输出：3 解释：将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。
提示：
- 树中节点的数目为
n 1 <= n <= 1000 <= Node.val <= n- 所有
Node.val的值之和是n
代码结果
运行时间: 22 ms, 内存: 16.0 MB
/*
* 题目思路：
* 使用递归方法处理树的遍历，Java Stream不适合直接处理树的结构。
* 这个解法与Java中的递归解法基本相同。
* 我们还是使用深度优先搜索（DFS）来计算每个节点的余额。
*/
class Solution {
private int moves;
public int distributeCoins(TreeNode root) {
moves = 0;
dfs(root);
return moves;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
moves += Math.abs(left) + Math.abs(right);
return node.val + left + right - 1;
}
}
解释
方法:
该题解采用了深度优先搜索(DFS)来解决问题。在遍历每个节点时，计算从该节点的左子树和右子树移动硬币所需的最小移动次数，并累加到全局变量 res 中。为每个节点定义一个返回值 (total_coins, total_nodes)，其中 total_coins 表示以当前节点为根的子树中所有节点的硬币总数，total_nodes 表示子树中节点的总数。对于每个节点，其需要的硬币数应为其节点数 (即 total_nodes)，因此其余硬币应向上或向下移动，移动的次数即为 abs(total_coins - total_nodes)。通过递归地计算每个节点的这两个值，并更新 res，最终得到全树的最小移动次数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在定义返回值(total_coins, total_nodes)时，total_coins和total_nodes具体代表什么含义？
▷🦆
如何理解移动次数是 abs(total_coins - total_nodes)，这里的计算逻辑是怎样的？
▷🦆
题解中提到的`累加左右子树的硬币移动次数`是如何影响最终结果的？能否具体解释这一过程？
▷🦆
在递归函数中，为什么要选择返回子树的总硬币数和总节点数，这样的设计有什么特别的考虑吗？
▷相关问题
树中距离之和
给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。
给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10] 解释: 树如图所示。 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
示例 2:
输入: n = 1, edges = [] 输出: [0]
示例 3:
输入: n = 2, edges = [[1,0]] 输出: [1,1]
提示:
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != bi- 给定的输入保证为有效的树
