Question

如何找到一个二叉树上最远的两个节点？

需要一个靠谱一些的算法

Answer 1

距离最远的两个节点就是深度最深的两个叶子结点。
我们可以对整个二叉树进行一次遍历，记录每个节点的深度，最远的两个节点一定是两个叶子节点。我们只需要在遍历过程中找到两个深度最深的叶子节点。那么这两个节点的距离就是最远的。整个算法的时间复杂度是O(n)，可以期望很快就能找到这两个相距最远的节点。

Answer 2

我们可以对整个二叉树进行一次遍历，记录每个节点的深度，最远的两个节点一定是两个叶子节点。我们只需要在遍历过程中找到两个深度最深的叶子节点。那么这两个节点的距离就是最远的。整个算法的时间复杂度是O(n)，可以期望很快就能找到这两个相距最远的节点。