查找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，但是当你到达根(即2)时，它会检查左边，因为上面的代码并返回-1，因为2的左边是空的，你返回-1为空。由于-1不等于0，此代码将返回-1而不是9的正确位置。有多种修复方法，但我将把它留给你。如果你仍然不知道如何修复它留下评论，我会提供一些选项