c - 打印键所在的树的级别

Question

1 - 读取 n 个数字的序列并将其插入二叉搜索树。（我做了这部分没有任何问题。）

Node *insert(Node **root, int k)
{
    if(*root == NULL)
    {
        Node *newNode = (Node *)malloc(sizeof(Node ));
        if(newNode == NULL)
            return NULL;
        newNode->key = k;
        newNode->left = NULL;
        newNode->right = NULL;
        (*root) = newNode; 
        return newNode; 
    }
    if(k < (*root)->key)
        return insert(&((*root)->left),k);
    else
        return insert((&(*root)->right),k);
}

2 - 读取一个数字并打印它所在的级别。如果键不存在于树中，则打印 -1。
这部分我不知道该怎么做，我只能计算出树的总高度。

int height(Node *aNode,int k) {
    if (aNode == NULL) {
        return -1;
    }

    int lefth = height(aNode->left,k);
    int righth = height(aNode->right,k);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

例子：

例子

如果给定的数字是60 ，我必须打印1

如果给定的数字是27 ，我必须打印3

如果给定的数字是100 ，我必须打印-1

标签： cbinary-search-tree

Answer 1

你应该：

• 0找到值时停止遍历并返回。
• -1当两个孩子都没有找到该值时返回。

int height(Node *aNode,int k) {
    if (aNode == NULL) {
        return -1;
    }

    if (aNode->key == k) return 0; /* add this */

    int lefth = height(aNode->left,k);
    int righth = height(aNode->right,k);

    if (lefth == -1 && righth == -1) return -1; /* add this */

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}