LeetCode 题解工作台
树中每个节点放置的金币数目
给你一棵 n 个节点的 无向 树，节点编号为 0 到 n - 1 ，树的根节点在节点 0 处。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 之间有一条边。 给你一个长度为 n 下标从 0 开始的整…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
根据题目描述，每个节点 的放置的金币数有两种情况： - 如果节点 对应的子树中的节点数目小于 ，那么放 个金币；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 n 个节点的 无向 树，节点编号为 0 到 n - 1 ，树的根节点在节点 0 处。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
给你一个长度为 n 下标从 0 开始的整数数组 cost ，其中 cost[i] 是第 i 个节点的 开销 。
你需要在树中每个节点都放置金币，在节点 i 处的金币数目计算方法如下：
- 如果节点
i对应的子树中的节点数目小于3，那么放1个金币。 - 否则，计算节点
i对应的子树内3个不同节点的开销乘积的 最大值 ，并在节点i处放置对应数目的金币。如果最大乘积是 负数 ，那么放置0个金币。
请你返回一个长度为 n 的数组 coin ，coin[i]是节点 i 处的金币数目。
示例 1：
输入：edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6] 输出：[120,1,1,1,1,1] 解释：在节点 0 处放置 6 * 5 * 4 = 120 个金币。所有其他节点都是叶子节点，子树中只有 1 个节点，所以其他每个节点都放 1 个金币。
示例 2：
输入：edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2] 输出：[280,140,32,1,1,1,1,1,1] 解释：每个节点放置的金币数分别为： - 节点 0 处放置 8 * 7 * 5 = 280 个金币。 - 节点 1 处放置 7 * 5 * 4 = 140 个金币。 - 节点 2 处放置 8 * 2 * 2 = 32 个金币。 - 其他节点都是叶子节点，子树内节点数目为 1 ，所以其他每个节点都放 1 个金币。
示例 3：
输入：edges = [[0,1],[0,2]], cost = [1,2,-2] 输出：[0,1,1] 解释：节点 1 和 2 都是叶子节点，子树内节点数目为 1 ，各放置 1 个金币。节点 0 处唯一的开销乘积是 2 * 1 * -2 = -4 。所以在节点 0 处放置 0 个金币。
提示：
2 <= n <= 2 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < ncost.length == n1 <= |cost[i]| <= 104edges一定是一棵合法的树。
解题思路
方法一：DFS + 排序
根据题目描述，每个节点 的放置的金币数有两种情况：
- 如果节点 对应的子树中的节点数目小于 ，那么放 个金币；
- 如果节点 对应的子树中的节点数目大于等于 ，那么我们需要取出子树中的 个不同节点，计算它们的开销乘积的最大值，然后在节点 处放置对应数目的金币，如果最大乘积是负数，那么放置 个金币。
第一种情况比较简单，我们只需要在遍历的过程中，统计每个节点的子树中的节点数目即可。
而对于第二种情况，如果开销都是正数，那么应该取开销最大的 个节点；如果开销中有负数，那么应该取开销最小的 个节点和开销最大的 个节点。因此，我们需要维护每个子树最小的 个开销和最大的 个开销。
我们先根据题目给定的二维数组 构建邻接表 ，其中 表示节点 的所有邻居节点。
接下来，我们设计一个函数 ，该函数返回一个数组 ，其中存储了节点 的子树中最小的 个开销和最大的 个开销（可能不足 个）。
在函数 中，我们将节点 的开销 加入数组 中，然后遍历节点 的所有邻居节点 ，如果 不是节点 的父节点 ，那么我们将 的结果加入数组 中。
然后，我们对数组 进行排序，然后根据数组 的长度 计算节点 的放置金币数目，更新 ：
- 如果 ，那么节点 的放置金币数目为 ，否则节点 的放置金币数目为 ；
- 如果 ，那么我们只需要保留数组 的前 个元素和后 个元素。
最后，我们调用函数 ，并且返回答案数组 即可。
时间复杂度 ，空间复杂度 。其中 是节点的数目。
class Solution:
def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
def dfs(a: int, fa: int) -> List[int]:
res = [cost[a]]
for b in g[a]:
if b != fa:
res.extend(dfs(b, a))
res.sort()
if len(res) >= 3:
ans[a] = max(res[-3] * res[-2] * res[-1], res[0] * res[1] * res[-1], 0)
if len(res) > 5:
res = res[:2] + res[-3:]
return res
n = len(cost)
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = [1] * n
dfs(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for traversing all nodes once with DFS and aggregating subtree costs. Space complexity is O(n) for storing children and cost tracking arrays in each node's state during traversal. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate considers DFS for full tree traversal and subtree aggregation.
- question_mark
Candidate identifies that leaf nodes always receive one coin as a base case.
- question_mark
Candidate correctly handles negative and zero costs in product calculation to avoid incorrect coin counts.
常见陷阱
外企场景- error
Forgetting to handle negative and zero costs leading to wrong coin numbers.
- error
Incorrectly tracking fewer than three largest/smallest costs, causing wrong product computation.
- error
Failing to store subtree results, resulting in repeated calculations and timeouts on large trees.
进阶变体
外企场景- arrow_right_alt
Compute coins using sum instead of product of subtree costs.
- arrow_right_alt
Find maximum coin placement in weighted n-ary trees instead of binary trees.
- arrow_right_alt
Determine minimum coins with modified rules for negative-only subtrees.