This question already has answers here:
Finding Center of The Tree
（3个答案）
在我试图解决的一个算法问题中，我遇到了一个给定树的情况，我需要选择一个节点作为根，树的高度将是最小的。
有200000个节点和150000个边。由于时间限制，我需要一个比
我可以使用什么算法？
（3个答案）
在我试图解决的一个算法问题中，我遇到了一个给定树的情况，我需要选择一个节点作为根，树的高度将是最小的。
有200000个节点和150000个边。由于时间限制，我需要一个比
O(n^2)更好的算法。我可以使用什么算法？
最佳答案
选择任意节点并假设它是根节点。运行DFS以查找到最远叶子的距离如果选择第一个节点作为根节点，这将基本上计算树的高度。
接下来，通过找到树的中心来找到合适的根。要执行此操作，请查看当前根的子级，并选择具有最大高度（到最远叶子的最大距离）的子级。如果将根移动到该子节点，则新高度将在该节点中已有的值和1+当前根的其他叶的下一个最大值之间为最小值你应用这个，移动根直到你不能再降低高度。这是树的一个中心（可能更多）和一个你正在寻找的解决方案。
初始dfs为o（n）。在优化距离时，不能访问一个节点两次，而且每个步骤都是o（1）摊销的，所以总的来说是o（n）。O（1）分期偿还，因为一个节点可以有很多子节点，但您只考虑它们一次（移动后不能返回，因此不能再次检查它们），所以即使检查整个树，也将总共检查O（N）个子节点。