C语言二叉搜索树中查找第N个元素的递归实现问题

原代码存在的问题 #

1. 空指针访问bug：函数开头直接访问tree->nodeCount，未先判断tree是否为NULL，触发空指针解引用错误。
2. 静态变量count逻辑混乱：
   • 递归调用左子树后未处理返回值，若左子树已找到目标节点，后续的count++和右子树递归会破坏计数状态。
   • 找到目标后重置count为0，但上层递归的count++会覆盖该值，导致后续函数调用的计数出错。
   • 静态变量会保留上一次调用的状态，多次调用函数时无法正确初始化。
3. 缺少默认返回值：当所有分支都未触发返回时，函数无返回语句，导致未定义行为。

修复方案1：基于中序遍历的递归实现（无静态变量隐患） #

通过辅助函数传递计数变量（指针方式），避免静态变量的全局状态问题：

// 递归辅助函数，用指针传递计数
static TreeNode* findNthHelper(int N, TreeNode* tree, int* count) {
    if (tree == NULL) {
        return NULL;
    }

    // 先遍历左子树
    TreeNode* leftResult = findNthHelper(N, tree->left, count);
    if (leftResult != NULL) {
        return leftResult;
    }

    // 处理当前节点
    (*count)++;
    if (*count == N) {
        return tree;
    }

    // 遍历右子树
    return findNthHelper(N, tree->right, count);
}

// 对外调用接口
TreeNode* findNthElement(int N, TreeNode* tree) {
    int count = 0;
    return findNthHelper(N, tree, &count);
}

修复方案2：利用nodeCount的高效实现（推荐） #

既然每个节点已维护自身子树的节点总数，可直接借助二叉搜索树的有序性快速定位目标，无需遍历所有节点，时间复杂度为O(h)（h为树高）：

TreeNode* findNthElement(int N, TreeNode* tree) {
    if (tree == NULL) {
        return NULL;
    }

    // 获取左子树的节点数，左子树不存在则为0
    int leftSubtreeCount = tree->left ? tree->left->nodeCount : 0;

    // 当前节点是第leftSubtreeCount+1个元素
    if (N == leftSubtreeCount + 1) {
        return tree;
    }
    // 目标在左子树中
    else if (N <= leftSubtreeCount) {
        return findNthElement(N, tree->left);
    }
    // 目标在右子树中，调整N为右子树中的相对位置
    else {
        return findNthElement(N - leftSubtreeCount - 1, tree->right);
    }
}

内容的提问来源于stack exchange，提问作者The Rodeo Expert