在C++中查找BST中特定节点的深度

Question

假设树的顺序如下: 2，9，4，7。我需要找到每个节点的深度:节点2-深度0，节点9-深度1，节点4-深度2，节点7-深度3。

2
 \
  9
 /
4
 \
  7

然而，我得到的输出是:节点2-深度0，节点9-深度-1，节点4-深度-1，节点7-深度-1。

我想我不能遍历右边的子树，因为每次左边都会变得大于零，并且函数在到达右边之前就退出了。但我不确定如何修复代码才能产生正确的输出。

我的代码：

int findDepth(Tree t, int key, int depth) {

    if (t == NULL) {
        return -1; 
    }

    if (t->value == key) {
        return depth;
    }

    int left = findDepth(t->left, key, depth + 1);
    if (left != 0) {
        return left; 
    }

    int right = findDepth(t->right, key, depth + 1); 
    if (right != 0) {
        return right; 
    }

    return 0; 

}

int treeNodeDepth(Tree t, int key) {

    return findDepth(t, key, 0);

}

Answer 1

当有节点和没有节点时，都调用int left = findDepth(t->left, key, depth + 1);。两者都可以，但如果您使用NULL调用，则应更新测试

   if (left != 0) {
        return left; 
    }

因此当从子树接收到-1时，您不会返回。

选项一，在调用之前进行测试：

if (t->left){
    int left = findDepth(t->left, key, depth + 1);
    if (left != 0) {
        return left; 
    }
}

选项二:更改测试：

int left = findDepth(t->left, key, depth + 1);
if (left > 0) {
    return left; 
}

第三个选项是更改空指针的返回值，以匹配上面的测试。

if (t == NULL) {
    return 0; 
}

Answer 2

问题就在这里

 int left = findDepth(t->left, key, depth + 1);
if (left != 0) {
    return left; 
}

假设你搜索9，但是当你到达root (即2)时，由于上面的代码，它会检查left，并返回-1，因为left of 2是null，而你返回的是-1。因为-1不等于0，所以这段代码将返回-1，而不是9的正确位置。有多种修复方法，但我将把它留给您。如果您仍然不知道如何修复它，请留言，我将提供一些选项