如何用C语言计算二叉搜索树(BST)中指定节点的深度

云上老周

2026-9-30

代码问题分析

致命逻辑错误：代码中root->left->data = depth(root->left, N)和root->right->data = depth(root->right, N)语句会直接修改二叉树节点的存储数据，完全破坏原树结构，这是得到错误结果的核心原因，不需要修改树的任何值，只需要接收递归的返回值做判断即可。
递归返回值处理错误：没有判断子树递归查找是否成功找到目标节点，直接对count做自增，会导致没找到节点时返回0而不是预期的-1。
可选优化：如果目标是通过指针匹配节点，直接比较root == N比比较data更准确，可避免BST存在重复值时的匹配错误。

修正后代码

int depth(Node *root, Node *N){
    // 空树直接返回-1，代表未找到
    if (root == NULL){
        return -1;
    }
    // 当前节点就是目标节点，深度为0
    if (root == N){ // 如果你确定要按data匹配，这里可以改回root->data == N->data
        return 0;
    }
    // 往左子树查找
    if (N->data < root->data){
        int left_depth = depth(root->left, N);
        // 左子树找到的话，当前深度是左子树深度+1，没找到就返回-1
        return left_depth == -1 ? -1 : left_depth + 1;
    }
    // 往右子树查找
    else {
        int right_depth = depth(root->right, N);
        return right_depth == -1 ? -1 : right_depth + 1;
    }
}