给定一棵树,如何在树中找到中心节点,以使从中心节点到其他节点的距离最小(假设每个边缘具有单位权重)?我正在尝试使用DFS,但是可以在线性时间内进行吗?
继续从树中删除叶节点,直到剩下一个节点为止(如果剩下两个节点,则删除其中一个节点)。该节点最大程度地减少了它与其他每个节点的最大距离。
例:
* * / \ \ * * * * \ \ \ * => * => * => * \ \ * * \ *
要在线性时间内实现此功能,请将所有初始叶节点插入FIFO队列中。对于每个节点,还存储其子节点数。从队列中删除元素时,请减少其父级的子级数。如果该数字变为零,则将父项插入队列。