algorithm - 多次遍历树时，如何计算任意节点被访问的最大次数？

Question

我们多次遍历给定的树(不是二叉树)。我们如何计算树中任何节点被访问的最多次数？

例如:在树中:

     1
   /   \
 2       3
       /   \
      4     5

假设我们被告知要旅行 2 次，从 2 到 3，然后 5 到 3。旅行路径将是(2->1->3 和 5->3)。一个节点被访问的最大次数是2(该节点是3)。所有的旅行都是相互独立的。给定的旅行从给定的节点 A 开始并在 B 结束。

考虑到我们有超过 50,000 个节点和 75,000 条路径要覆盖(例如示例中的 2 到 3 和 3 到 4)，如何有效地旅行(如果我们甚至需要)来计算它？

Answer 1

根据您所说的，答案是该节点拥有的子节点数量...

同样在您的示例中，根据您所说的，1 和 3 的访问次数最多。

在您的示例中，每个节点只会被访问一次。您可以多次访问一个节点的唯一方法是使用像这样的树:

          1     3
            \ /
             2

Edit::最有效的遍历方式是如果你有一个完美的二叉树

   4
 2   6
1 3 5 7

其中最大深度是 ((log base 2 of (number of nodes + 1)) + 1) 向下舍入的数量