Java 中创建互质树

给定的二叉树的边是无向的，并且节点是连接的。此外，该树不是循环的。二叉树由 t 个节点组成，编号从 0 到 t - 1，并且有 t - 1 条边。树的每个节点都包含一些值。第 0 个节点是树的根节点。二叉树使用数组表示。一个数组是 nodeArr[]，它显示了每个节点关联的值。另一个数组是二维的 edgeArr[][]。nodeArr[j] 显示第 j 个节点的值，edgeArr[j] = [pj, qj] 表示 pj 节点和 qj 节点之间存在一条边。

我们的任务是创建一个并打印一个大小为 t 的数组，在本例中为 ansArr[]，使得 ansArr[i] 显示第 i 个节点的有效祖先。有效祖先是指最接近第 i 个节点的祖先或节点，使得祖先节点的值与第 i 个节点的值的最大公约数是 1，即两个值必须互质。

为简单起见，假设二叉树节点的值始终小于或等于 50。

示例 1

输入： nodeArr[] = {12, 13, 13, 12}, edgeArr[][] = {{0, 1}, {1, 2}, {1, 3}}

输出： ansArr[] = {-1, 0, 0, 1}

解释： 节点值在括号中注明（见上图）。根节点没有祖先。因此，ansArr[0] 的值为 -1。节点 1 的祖先是根节点 0。如果计算节点 0 和节点 1 的值的最大公约数，我们得到 gcd(12, 13) = 1，这使得 12 和 13 互质。因此，根节点是节点 1 的有效祖先。因此，ansArr[1] = 0，因为第 0 个节点是根节点。

对于节点 2，最近的祖先是节点 1，它们值的最大公约数是 (gcd(13, 13) = 13)，不等于 1。因此，我们向上移动一步，到达节点 0。再次计算它们值的最大公约数。gcd (12, 13) = 1。因此，第 0 个节点是节点 2 的有效祖先。因此，ansArr[2] = 0。

对于节点 3，最近的祖先是节点 1，它们值的最大公约数是互质的，因为 gcd(13, 12) = 1。因此，节点 3 的有效祖先是节点 1。因此，ansArr[3] = 1。

示例 2

输入： nodeArr[] = {15, 16, 10, 12, 13, 16, 15}, edgeArr[][] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}}

输出： ansArr[] = {-1, 0, -1, 0, 0, 0, -1}

暴力破解法

基本概念是遍历整个二叉树。对于遍历过程中的每个节点，计算最近的互质祖先。

步骤 1： 使用 DFS 遍历整个二叉树。

步骤 2： 创建一个 findGCD() 方法来计算任意两个数的最大公约数。

步骤 3： 对于每个节点，从下到上遍历其所有祖先，以验证它们是否互质。在最坏情况下，不会有任何祖先与所选节点的最大公约数（使用 findGCD() 方法计算最大公约数）为 1。对于这些节点，在 ansArr 中放置 -1。如果找到有效的祖先，则将其索引放入数组 ansArr[] 中。

实施

观察上述算法的实现。

文件名： GetCoPrimeSol.java

输出

For the first input:
For node 0 the valid ancestor is: -1
For node 1 the valid ancestor is: 0
For node 2 the valid ancestor is: 0
For node 3 the valid ancestor is: 1

For the second input:
For node 0 the valid ancestor is: -1
For node 1 the valid ancestor is: 0
For node 2 the valid ancestor is: -1
For node 3 the valid ancestor is: -1
For node 4 the valid ancestor is: 1
For node 5 the valid ancestor is: 0
For node 6 the valid ancestor is: -1

解释： 由于上述程序有嵌套循环，因此它的时间复杂度是二次的。

由于时间复杂度是二次的，上述解决方案未得到优化。我们可以通过记忆化来优化。观察以下方法。

优化方法

步骤 1： 从输入创建图。

步骤 2： 预先计算 1 到 50 之间数字对的最大公约数，并将它们存储在一个（对称）矩阵中：O(50*50)。

步骤 3： 对图执行 BFS。在 BFS 过程中，将遇到的每个节点的父节点存储在一个映射中，例如 path，并使用 path 执行回溯以使用预计算矩阵查找与当前节点互质的当前节点的祖先。

步骤 4： 务必在回溯过程中使用记忆化，以避免时间限制超出。

实施

观察上述算法的实现。

文件名： GetCoPrimeSol1.java

输出

For the first input:
For node 0 the valid ancestor is: -1
For node 1 the valid ancestor is: 0
For node 2 the valid ancestor is: 0
For node 3 the valid ancestor is: 1

For the second input:
For node 0 the valid ancestor is: -1
For node 1 the valid ancestor is: 0
For node 2 the valid ancestor is: -1
For node 3 the valid ancestor is: -1
For node 4 the valid ancestor is: 1
For node 5 the valid ancestor is: 0
For node 6 the valid ancestor is: -1

解释： 由于记忆化，上述程序的时间复杂度为 O(n * log(n))，其中 n 是树中节点的总数。