C语言实现BST特定节点深度查找返回异常如何修复

问题根源 #

代码所有非根节点都返回-1，本质是两个逻辑错位：

• 递归查找的“未找到”返回值不统一：空节点分支直接返回-1，但遍历完当前子树仍未命中的分支返回0，两个值都被后续判断当成了有效查找结果
• 子树结果的判断条件错配：代码写的判断逻辑是if (left != 0) return left，意思是只要左子树返回值不是0就直接退出查找，根本不检查这个返回值是“找到的合法深度”还是“未找到的错误标记”。

拿查找节点9的实际流程举例就能看懂问题：

1. 从根节点2开始查找，左子树为空
2. 递归查左子树时进入空节点分支，返回-1
3. 回到上层拿到left=-1，刚好满足left !=0的判断条件，直接把-1返回出去，完全不会执行查找根节点右子树（节点9所在分支）的代码

具体修改点 #

树节点的合法深度都是从0开始的非负整数，我们完全可以统一用-1作为全函数的“未找到目标”的固定标记，调整逻辑即可：

• 把所有未找到场景的返回值统一为-1，替换原来遍历结束返回0的错误写法
• 左、右子树的判断逻辑改为：只有子树返回值不是-1（也就是真正找到了目标）时，才直接返回该结果；如果子树返回-1（未找到），再继续查找另一棵子树
• 全树遍历完都没找到目标时，最终返回-1

修正后的完整代码：

int findDepth(Tree t, int key, int depth) {
    // 空节点：未找到，返回统一标记-1
    if (t == NULL) {
        return -1; 
    }
    // 命中目标：返回当前累计的深度
    if (t->value == key) {
        return depth;
    }
    // 优先查找左子树
    int left = findDepth(t->left, key, depth + 1);
    // 左子树找到目标，直接返回结果
    if (left != -1) {
        return left; 
    }
    // 左子树未找到，查找右子树
    int right = findDepth(t->right, key, depth + 1); 
    // 右子树找到目标，直接返回结果
    if (right != -1) {
        return right; 
    }
    // 左右子树都未找到，返回统一未找到标记
    return -1; 
}

int treeNodeDepth(Tree t, int key) {
    return findDepth(t, key, 0);
}

效果验证 #

用题目给出的树结构测试，输出完全符合预期：

• 节点2：查找时直接命中，返回初始传入的depth=0
• 节点9：根节点左子树为空返回-1，进入右子树递归，累计depth=1时命中，返回1
• 节点4：遍历到右子树的节点9后，进入其左子树递归，累计depth=2时命中，返回2
• 节点7：遍历到节点4后，进入其右子树递归，累计depth=3时命中，返回3

内容的提问来源于stack exchange，提问作者J Szum