寻找快速算法在二叉树中找到两个节点之间的距离

Question

如何在二叉树中找到两个节点之间的距离？同样,有哪些算法可以找到两个节点的最新共同祖先(最低共同祖先)？

Answer 1

1. 计算每个节点的祖先列表
2. 找到公共前缀
3. 公共前缀的最后一个元素是最低共同祖先
4. 从两个祖先列表中删除公共前缀
5. 距离是剩余列表+1的长度之和

Answer 2

找到共同祖先几乎肯定是更容易的任务。这是一个非常简单的过程：从树的根开始，沿着树下降，直到到达一个节点，在该节点中，您必须下降到不同的子节点才能到达相关的两个节点。该节点是公共父节点（当然，假设树包含两个节点）。