Я пытаюсь найти высоту бинарного дерева с помощью этого кода, но оно продолжает возвращать 0, может кто-нибудь сказать мне, почему?

Question

Я пытаюсь найти высоту бинарного дерева с помощью этого кода, но оно продолжает возвращать 0, может кто-нибудь сказать, почему?

int heightHelper(Node* root, int maxheight, int rootheight)
{

    if (root->right == nullptr && root->left == nullptr) { //checks if the node has a child
        if (maxheight < rootheight) {
            maxheight = rootheight;
        }
    }
    else { //if it has then increase height by 1
        rootheight += 1;

        if (root->left != nullptr) {
            heightHelper(root->left, maxheight, rootheight);
        }
        if (root->right != nullptr) {
            heightHelper(root->right, maxheight, rootheight);
        }
    }

    return maxheight; //return height
}

int height(Node* root)
{
    // Write your code here.

    return heightHelper(root, 0, 0); //root node base case
}

Answer 1

Вы смешиваете два способа ведения дел. Либо передайте параметр результата , используя указатель или адрес (int* и &maxheight). В этом случае нет возвращаемого значения. Но это стиль кодирования, который я видел в основном только в аппаратном программировании.

В противном случае вы можете вернуть результат. У вас уже есть возвращаемый параметр, просто исправьте фактическое использование значения, потому что ваш код его игнорирует.

Вот два способа сделать это:

Используя параметр возврата:

int heightHelper(Node* root, int height)
{

    if (root->right == nullptr && root->left == nullptr) { //checks if the node has a child
        return height;
    }
    else { //if it has then increase height by 1
        height += 1;
        int maxheight1;
        int maxheight2;

        if (root->left != nullptr) {
            maxheight1 = heightHelper(root->left, height);
        }
        if (root->right != nullptr) {
            maxheight2 = heightHelper(root->right, height);
        }

        // return maximum of the two
        if (maxheight1 > maxheight2) return maxheight1;
        else return maxheight2;
    }
}

int height(Node* root)
{
    // Write your code here.

    return heightHelper(root, height); //root node base case
}

Использование параметров указателя. Обратите внимание, что rootheight является локальным для каждой ветви, поэтому не передавайте его как указатель.

void heightHelper(Node* root, int* maxheight_ptr, int rootheight)
    {

    if (root->right == nullptr && root->left == nullptr) { //checks if the node has a child
        if (*maxheight < rootheight) {
            *maxheight = rootheight;
        }
    }
    else { //if it has then increase height by 1
        rootheight += 1;

        if (root->left != nullptr) {
            heightHelper(root->left, maxheight_ptr, rootheight);
        }
        if (root->right != nullptr) {
            heightHelper(root->right, maxheight_ptr, rootheight);
        }
    }
}

int height(Node* root)
{
    // Write your code here.

    int maxheight = 0;


    heightHelper(root, &maxheight, 0); //pass the addresses of variables

    return maxheight;
}