Найти количество уровней от одного узла к другому

Question

Я пытаюсь написать функцию, которая будет возвращать количество уровней от одного узла к другому в четырехугольном дереве.

Вот что у меня есть, но я уверен, что это неправильно, я просто не могу понять, почему:

int levels(QtreeNode * orig, QtreeNode * n) {

    //calculates the number of levels from orig to n
    if(orig==n)
        return 0;
    if(!orig->isLeaf())
        return 1 + levels(orig->nwChild, n) + levels(orig->neChild, n) + levels(orig->swChild, n)+ levels(orig->seChild, n);
    return 0;   

}

Есть идеи?

Answer 1

ваша ошибка в том, что вы добавляете уровни на пути к тупикам, но вам нужно рассчитать, как связаны два узла

int levels(QtreeNode * orig, QtreeNode * n)
{
    int path;

    // found!
    if (orig == n)
        return 0;
    // it's dead end, do not calc that way
    if (orig->isLeaf())
        return -1;
    path = levels(orig->nwChild, n);
    // not dead end? it's fine, return that path
    if (path >= 0)
        return 1 + path;
    path = levels(orig->neChild, n);
    // not dead end? it's fine, return that path
    if (path >= 0)
        return 1 + path;
    path = levels(orig->swChild, n);
    // not dead end? it's fine, return that path
    if (path >= 0)
        return 1 + path;
    path = levels(orig->seChild, n);
    // not dead end? it's fine, return that path
    if (path >= 0)
        return 1 + path;
    // there is no path between this nodes
    return -2;
}