Abstand zwischen zwei Knoten in einem Baumalgorithmus Problem

Question

Ich muss den Abstand zwischen zwei Knoten in einem Baum berechnen. I implementiert die allgemeine Formel:

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

Der Code funktioniert für die meisten der Eingabe, aber wenn ich mit (Vater, Sohn) versuche ich den falschen Abstand zu bekommen. Hier ist mein Code:

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); 
} 

Für den einfachen Baum:

A 
B C 
D E F G 

Wir wissen, dass die Dist (C, G) = 1, aber mein Algorithmus 3. Irgendwelche Ideen zurückkehrt?

Answer 1

Bitte stellen Sie die Implementierung der Methode lca zur Verfügung, damit wir prüfen können, ob es richtig funktioniert. Ich bin mir ziemlich sicher distance gibt 3 zurück, weil lca(node1, node2) null ist. In diesem Fall ist lca == null wahr, und das Verfahren kehrt

node1.getNumberOfAncestors() + node2.getNumberOfAncestors()

die im Grunde

node1.getNumberOfAncestors() = 1 für C +

node2.getNumberOfAncestors() = 2 für G = 3