相关疑难解决方法(0)

给定一棵树,如何在树中找到中心节点,使得从中心节点到其他节点的距离最小(假设每条边具有单位重量)？我正在尝试使用DFS但是可以在线性时间内完成吗？

我有一个问题,这是我的计划的一部分.

对于树T =(V,E),我们需要在树中找到节点v,其最小化从v到任何其他节点的最长路径的长度.

那么我们如何找到树的中心？是否只能有一个中心或更多？

如果有人能为我提供良好的算法,那么我就可以了解如何融入我的计划.

问题是找出BinarySearchTree的每两个节点之间的距离之和,假设每个父子对由单位距离分开.每次插入后都要计算.

例如:

 ->first node is inserted..

      (root)

   total sum=0;

->left and right node are inserted

      (root)
      /    \
  (left)   (right)

   total sum = distance(root,left)+distance(root,right)+distance(left,right);
             =        1           +         1          +         2
             =     4

and so on.....

我提出的解决方案:

1. 蛮力.脚步:

   1. 执行DFS并跟踪所有节点:O(n).
   2. 选择每两个节点并O(nC2)_times_O(log(n))=O(n2log(n))使用最低公共祖先方法计算它们之间的距离并将它们相加.

   整体复杂性:-O(n2log(n)).

2. O(nlog(n)).脚步:-

   1. 在插入之前执行DFS并跟踪所有节点:O(n).
   2. 计算插入节点与之间的距离:O(nlog(n)).剩下的节点.
   3. 使用步骤2中计算的总和添加现有总和

   整体复杂性:-O(nlog(n)).

现在的问题是"是否存在任何解决方案O(n)？