在树中查找所有最长的唯一路径
让我们假设我们有一棵由N个节点组成的树。 任务是查找树中所有最长的唯一路径。 例如，如果树看起来如下所示：
然后树中有三条最长的独特路径：1 - 2 - 3 - 4 - 5，6 - 2 - 3 - 4 - 5和1 - 2 - 6。
我想以编程方式查找并存储给定树的所有这些路径。 一种方法是计算树中每对节点之间的路径，然后拒绝包含在任何其他路径中的路径。 但是，我正在寻找一种有效的方法来做到这一点。 我的问题如下：
我想试用它的原因是因为我试图解决这个问题：KNODES
一个时间复杂度低于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)的算法，
据我所知，你有一棵没有选定根的树。 您的允许路径是不允许两次访问树节点的路径（您不允许返回）。 而且你需要找到所有可允许的路径，这些路径不是任何允许路径的子路径。
所以如果我理解正确的话，那么如果一个节点只有一条边，那么可允许的路径就在这个节点上开始或停止。 如果连接了树，则可以通过一条允许的路径从任意节点到达任何节点。
因此，您选择所有具有一条边的节点，将其称为S.然后选择一个S并遍历整个树，将路径保存到结尾（路径，而不是步序）。 然后，您可以对S中的每个其他项目执行此操作，并删除重复的路径（它们可以按相反的顺序：例如从1：1 - 2 - 6开始，从6：6 - 2 - 1开始）。
因此，在这里，您必须访问树中所有节点的次数与树中的叶节点数相同。 所以复杂性取决于分支因子（在最坏的情况下，它是O（n ^ 2））。有一些优化可以减少操作的数量，就像你不必从S末尾走树一样。
在这张图中，最长的路径是{1,2,3,4}，{1,2,3,5}，{1,2,3,6}，{1,2,3,7}，{1，2，3， 2，3，8}，{1,2,3}，{1,2,3，10}
像这样的树存储所有最长的路径将花费你O（N2）
链接地址: http://www.djcxy.com/p/28399.html