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