树中两个节点之间的距离算法问题

我需要计算树中两个节点之间的距离。我实现了通式：树中两个节点之间的距离算法问题

Dist(n1,n2) = Dist(root,n1), Dist(root,n2) - 2*Dist(root,lca)

代码适用于大多数的投入，但如果我尝试用（父亲，儿子）我得到错误的距离。这里是我的代码：

public static int distance(Tree t, Node<String> node1, Node<String> node2) 
{ 
    Node<String> lca = lca(node1, node2); 
    //This if statement is when the input contains the root itself 
    //this means that the distance is simply from the node and the root 
    if(lca==null) 
    { 
     // the function getNumberOfAncestors returns exactly the distance between a generic node and the root, since I count parent by parent and so on. 
     return node1.getNumberOfAncestors() + node2.getNumberOfAncestors(); 
    } 

    return node1.getNumberOfAncestors() + node2.getNumberOfAncestors() - 2*distance(t, t.getRoot(), lca); 
}

对于简单的树：

A 
B C 
D E F G

我们知道，DIST（C，G）= 1，但我的算法返回3 任何想法？

来源

2016-10-23 user840718

试试BFS。它非常简单，记录完备，并且还会为您提供启动节点和其他任何节点之间的最短路径。 – beatngu13

对于调试，首先应打印node1.getNumberOfAncestors（），node2.getNumberOfAncestors（）和distance（t，t.getRoot（），lca）。查看所有3个值是否正确。编辑：也有一个原因，你不使用lca的getNumberOfAncestors（）？ –

请提供lca方法的实现，以便我们检查它是否以正确的方式工作。我很确定distance返回3，因为lca(node1, node2)为空。在这种情况下 lca == null为真，并且该方法返回

node1.getNumberOfAncestors() + node2.getNumberOfAncestors()

这基本上是

node1.getNumberOfAncestors() = 1为C +

node2.getNumberOfAncestors() = 2为G = 3

来源

2016-10-23 10:14:53 ncw

树中两个节点之间的距离算法问题

回答

相关问题