我想计算树中两个任意节点之间的路径(在Java中实现)。文献中有解决方法吗?
10(root)
/
8 11
/
7 9 15
距离(7,9)= 2
我们可以计算距离(root, 7) = 2，计算距离(root, 9) = 2, LCA(7,9) = 8。LCA代表"最低共同祖先"，因此distance(7, 9) = distance(root, 7) + distance(root, 9) - 2*distance(root, LCA) = 2 + 2 - 2*1 = 2
现在你可以看到方法;真正的问题是如何计算距离(root, anyNode)。这是一个常见的问题，我想你应该很快就能找到如何找到到任何想要的节点的距离。
可以使用共同祖先计算树中两个节点之间的距离。
应该是这样的:
Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)