选择树的根，使树的高度最小
Choosing a root of a tree so that the tree height is minimum
在我试图解决的算法问题中 - 我遇到了一棵树，我需要 select 一个节点作为树的根节点最小值。
有 200,000 个节点和 150,000 条边。由于时间限制，我需要一个比 O(n^2).
更好的算法
我可以使用什么算法？
我认为树的中心应该是作为树根的所需节点，因为如果根是树的中心，则从根到任何节点的最大距离最小。
选择任何节点并假设它是根。 运行 一个 DFS 来寻找到最远叶子的距离。如果您选择第一个节点作为根，这将基本上计算树的高度。
接下来您通过找到树的中心来找到正确的根。为此，您查看当前根的 children 并选择高度最大的那个（到最远叶子的距离最大）。如果将根移动到那个 child ，新高度将是您在该节点中已有的值和 1 + 当前根的其他叶子的下一个最大值之间的最小值。你应用它，移动根直到你不能再降低高度。那是树的一个中心（可能更多）和您正在寻找的解决方案。
初始DFS为O(N)。在优化距离时，您不能两次访问一个节点，并且每一步都是 O(1) 摊销的，所以总体来说是 O(N)。 O(1) 摊销因为一个节点可以有很多 children 但你只考虑它们一次（移动后你不能回去所以你不能再次检查它们）所以即使你检查整个你总共要检查 O(N) children 树。
在我试图解决的算法问题中 - 我遇到了一棵树，我需要 select 一个节点作为树的根节点最小值。
有 200,000 个节点和 150,000 条边。由于时间限制，我需要一个比 O(n^2).
我可以使用什么算法？
我认为树的中心应该是作为树根的所需节点，因为如果根是树的中心，则从根到任何节点的最大距离最小。
选择任何节点并假设它是根。 运行 一个 DFS 来寻找到最远叶子的距离。如果您选择第一个节点作为根，这将基本上计算树的高度。
接下来您通过找到树的中心来找到正确的根。为此，您查看当前根的 children 并选择高度最大的那个（到最远叶子的距离最大）。如果将根移动到那个 child ，新高度将是您在该节点中已有的值和 1 + 当前根的其他叶子的下一个最大值之间的最小值。你应用它，移动根直到你不能再降低高度。那是树的一个中心（可能更多）和您正在寻找的解决方案。
初始DFS为O(N)。在优化距离时，您不能两次访问一个节点，并且每一步都是 O(1) 摊销的，所以总体来说是 O(N)。 O(1) 摊销因为一个节点可以有很多 children 但你只考虑它们一次（移动后你不能回去所以你不能再次检查它们）所以即使你检查整个你总共要检查 O(N) children 树。