打印key所在树的层级

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;
    }
}

示例：

bst example

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

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

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

Answer 1

你应该：

找到值后return0停止遍历
Return -1 当两个 children.

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;
    }
}

打印key所在树的层级

Print the level of the tree where a key is located

c

binary-search-tree