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

Question

我需要计算树中两个节点之间的距离。 我实施了一般公式：

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。 有什么想法吗

Answer 1

请提供lca方法的实施，以便我们检查其是否正确。我很确定distance返回3，因为lca(node1, node2)是空的。在这种情况下 lca == null为true，该方法返回

node1.getNumberOfAncestors() + node2.getNumberOfAncestors()

基本上

对于C+

G=3的node2.getNumberOfAncestors() = 2