LeetCode 题解工作台
互质树
给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。 给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。 nums[i] 表示第 i 个点的值， edges[j] = […
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
由于题目中 的取值范围为 $[1, 50]$，因此我们可以预处理出每个数的所有互质数，记录在数组 中，其中 表示 的所有互质数。 接下来我们可以使用回溯的方法，从根节点开始遍历整棵树，对于每个节点 ，我们可以通过 数组得到 的所有互质数。然后我们枚举 的所有互质数，找到已经出现过的且深度最大的祖先节点 ，即为 的最近的互质祖先节点。这里我们可以用一个长度为 的栈数组 来获取每个…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。
给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。
当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。
从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。
请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。
示例 1：
输入：nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]] 输出：[-1,0,0,1] 解释：上图中，每个节点的值在括号中表示。 - 节点 0 没有互质祖先。 - 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。 - 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。 - 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。
示例 2：
输入：nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] 输出：[-1,0,-1,0,0,0,-1]
提示：
nums.length == n1 <= nums[i] <= 501 <= n <= 105edges.length == n - 1edges[j].length == 20 <= uj, vj < nuj != vj
解题思路
方法一：预处理 + 枚举 + 栈 + 回溯
由于题目中 的取值范围为 ，因此我们可以预处理出每个数的所有互质数，记录在数组 中，其中 表示 的所有互质数。
接下来我们可以使用回溯的方法，从根节点开始遍历整棵树，对于每个节点 ，我们可以通过 数组得到 的所有互质数。然后我们枚举 的所有互质数，找到已经出现过的且深度最大的祖先节点 ，即为 的最近的互质祖先节点。这里我们可以用一个长度为 的栈数组 来获取每个出现过的值 的节点以及其深度。每个栈 的栈顶元素就是最近的深度最大的祖先节点。
时间复杂度 ，空间复杂度 。其中 为节点个数，而 为 的最大值，本题中 。
class Solution:
def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
def dfs(i, fa, depth):
t = k = -1
for v in f[nums[i]]:
stk = stks[v]
if stk and stk[-1][1] > k:
t, k = stk[-1]
ans[i] = t
for j in g[i]:
if j != fa:
stks[nums[i]].append((i, depth))
dfs(j, i, depth + 1)
stks[nums[i]].pop()
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
f = defaultdict(list)
for i in range(1, 51):
for j in range(1, 51):
if gcd(i, j) == 1:
f[i].append(j)
stks = defaultdict(list)
ans = [-1] * len(nums)
dfs(0, -1, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * V) where V is the number of unique values (≤50), due to iterating over potential coprime ancestors at each node. Space complexity is O(n + V) to store the tree structure, recursion stack, and value-to-node maps. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect an efficient solution that avoids recomputing gcd repeatedly for same values.
- question_mark
Check whether candidate ancestors are updated correctly on DFS exit to maintain path accuracy.
- question_mark
Confirm that all edge cases with repeated values and root-only coprime scenarios are handled.
常见陷阱
外企场景- error
Not restoring ancestor mappings after returning from DFS recursion leads to incorrect ancestor assignments.
- error
Failing to precompute or cache coprime relationships causes TLE on large trees.
- error
Assuming nearest coprime ancestor is always immediate parent, ignoring higher ancestors in path.
进阶变体
外企场景- arrow_right_alt
Modify the problem to return all coprime ancestors for each node instead of only the nearest.
- arrow_right_alt
Allow dynamic updates to node values and query closest coprime ancestors after each update.
- arrow_right_alt
Limit node values to prime numbers and observe how coprime checks simplify.