Уровень узла в двоичном дереве

Question

Почему уровень узла не печатается?Уровень повышается после каждого звонка? Где проблема в коде?

int levelNode(struct Node* root,int a,int level){
    if(root==NULL){
        return 0;
    }
    if(root->key==a){
        return level;
    }
    levelNode(root->left,a,level+1);
    levelNode(root->right,a,level+1);
}

Answer 1

Ауууууууууууу, а сколько рекурсии!Просто хотел указать, что рекурсия абсолютно злая, и я лично избегаю ее везде, где могу (на самом деле, вы всегда можете избежать этого).

Просто чтобы найти альтернативное решение здесь, в этой теме.Если ваше дерево отсортировано, вы можете просто сделать:

int levelNode(struct Node* root, int a)
{
    node *temp = root;
    int level = 0;
    while (temp != NULL)
    {
        if (temp->data == a)
            break;
        level ++;
        if (a > temp->data)
            temp = temp->right;
        else if (a < temp->data)
            temp = temp->left;
    }
    if (temp == NULL)
        return 0;
    if (temp->data == a)
        return level;
    return 0;
}

В случае, если ваше дерево не отсортировано, вы можете немного адаптировать мой код, чтобы сделать «правильную» полноценную BFS.

Как то так:

#include <stdio.h>
#include <queue>
#include <map>

int levelNode(struct Node* root, int a)
{

    std::queue<Node*> stack;
    std::map<Node*, int> xmap;
    stack.push(root);
    xmap[root] = 0;


    while (!queue.empty())
    {
        Node* f = queue.front();
        if(f == NULL) return;

        queue.pop();

        if(f->data == a) return xmap[f];

        if(f->left){
            queue.push(f->left);
            xmap[f->left] = xmap[f]+1;
        }
        if(f->right){
            queue.push(f->right);
            xmap[f->right] = xmap[f]+1;
        }
    }

    return 0;
}

Answer 2

Должно быть как

int levelNode(struct Node* root,int a,int level){
    int found;
    if(root==NULL){
        return 0;
    }

    if(root->key==a){
        return level;
    }

    found = levelNode(root->left,a,level+1);
    if (found != 0) return found;

    found = levelNode(root->right,a,level+1);
    if (found != 0) return found;

    return 0; 
}