LeetCode每日一题：1766.互质树

LeetCode 每日一题 ---- 【1766. 互质树】

• 1766.互质树
  • • 方案一：预处理结合深度优先搜索

互质树问题解析

方法一：预处理+DFS

针对节点 x，需要确定其最近的祖先节点，该祖先节点的数值与 nums[x] 互质。

最直接的方式是遍历 x 的所有祖先节点。然而，若这棵树构成一条链状结构，则遍历所有祖先的时间复杂度为 O(n)，对每个节点都进行此类操作会导致整体时间复杂度达到 O(n²)，效率较低。

考虑到所有节点的数值均不超过 50，可以尝试枚举 [1,50] 范围内与 nums[x] 互质的所有数值。由于目标是找到「最近」的祖先，在多个具有相同数值的祖先中，只需关注深度最大的那个。因此，对于每个节点 x 来说，最多只需要检查 50 个可能的祖先。通过这种方式，总的时间复杂度可控制在 O(nU) 范围内，其中 U=50。

具体实施过程中，在递归遍历树结构的同时需维护两组信息：

valDepth 数组。该数组中 valDepth[j] 记录的是当前路径上数值为 jjj 的最近祖先所处的深度值。

valNodeId 数组。该数组中 valNodeId[j] 存储的是当前路径上数值为 jjj 的最近祖先对应的节点编号。

假设当前处理的节点值为 val=nums[x]，则从 [1,50] 中筛选出所