algorithm - 树中的中心节点

Question

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

Answer 1

不断从树中删除叶节点，直到只剩下一个节点(如果只剩下两个节点，请删除其中任何一个)。该节点最小化从它到每个其他节点的最大距离。

例子:

   *                 *              
  / \                 \
 *   *                 *              *
      \                 \              \
       *      =>         *     =>       *    =>   *
        \                 \                     
         *                 *
          \
           *

要在线性时间内实现这一点，请将所有初始叶节点插入 FIFO queue 中.对于每个节点，还存储其子节点的数量。从队列中删除元素时，减少其父元素的子元素数量。如果此数字变为零，则将父级插入队列。