algorithm - 查找树中所有最长的唯一路径

Question

让我们假设我们有一棵包含 N 个节点的树。任务是找到树中所有最长的唯一路径。例如，如果树如下所示:

然后树中有三个最长的唯一路径:1 - 2 - 3 - 4 - 5, 6 - 2 - 3 - 4 - 5 和 1 - 2 - 6。

我想以编程方式查找并存储给定树的所有此类路径。 一种方法是计算树中每对节点之间的路径，然后拒绝包含在任何其他路径中的路径。但是，我正在寻找一种有效的方法来做到这一点。我的问题如下:

• 是否有可能在不到 O(N^2) 的时间内计算出这些信息？我一直想不出比 O(N^2) 更快的解决方案。
• 如果是，能否请您指导我找到解决方案。

之所以想尝试一下，是因为我正在尝试解决这个问题:KNODES

Answer 1

时间复杂度低于 O(N^2) 的算法 可能 只存在于具有 N 个节点的树的每个解决方案可以在小于 O(N^2) 的空间内进行编码。

假设一个完整的二叉树有 n 个叶子 (N=n log n)。该问题的解决方案将包含每组 2 个叶子的路径。这意味着，解决方案将包含 O(n^2) 元素。因此对于这种情况，我们可以将解决方案编码为 2 元素叶子集。

现在考虑一个具有 m 个叶子的几乎完整的二叉树，它是通过从一个具有 n 个叶子的完整二​​叉树中删除任意叶子而创建的。将此树的解决方案与完整二叉树的解决方案进行比较时，两者将共享一组可能为空的路径。事实上，对于一棵完全二叉树的解的路径的每个子集，将存在至少一个具有 m 叶子的二叉树，如上所述，它包含这样一个子集的每个解。 (我们有意忽略了一个事实，即具有 m 个叶子的树在解决方案中可能有更多路径，其中至少一些路径末端不是完整二叉树的叶子。)

只有 m 个叶子的二叉树的解决方案的那一部分将由具有 (n^2)/2 位的数字编码。此数字中的位索引表示具有 n 列和行的矩阵右上半部分中的一个元素。

对于 n=4 这将是:

x012
xx34
xxx5

如果无向路径 row(i),column(i) 包含在解中，索引 i 处的位将被设置。

正如我们已经声明的那样，具有 m 个叶子的树的解决方案可能包含具有 n>=m 个叶子的完整二​​叉树的解决方案的任何子集，每个具有 (n^2)/2 位的二进制数将代表具有 m 个叶子的树的解决方案。

现在用 (n^2)/2 位编码每个可能的数字，小于 (n^2)/2 是不可能的。所以我们已经证明解决方案至少需要 O(n^2) 空间来表示。使用上面的 N=n log n 我们得到至少 O(N^2) 的空间要求。

因此不存在时间复杂度小于O(N^2)的算法