二叉树中序遍历C语言实现LeetCode提交不通过问题排查

核心错误点 #

• 违背LeetCode接口调用约定：inorderTraversal的入参returnSize是LeetCode侧已经分配好内存的输出参数，你不需要为它申请内存。你代码中执行returnSize = malloc(sizeof(int));直接修改了指针本身的指向，后续所有对*returnSize的赋值都写入了新申请的内存地址，LeetCode读取的原始地址中存储的长度值始终为0，最终判定返回的数组为空，所以输出仅显示]。
• 小优化点：当前helper函数中*returnSize == 0走malloc、其余走realloc的分支可以省略，因为realloc传入NULL指针时的行为和malloc完全一致，直接统一写*result_ref = realloc(*result_ref, sizeof(int) * (*returnSize + 1));即可。

修复后的代码 #

void inOrderTraversalHelper(struct TreeNode* root, int* returnSize, int** result_ref) {
    if (root != NULL) {
        inOrderTraversalHelper(root->left, returnSize, result_ref);        
        *result_ref = realloc(*result_ref, sizeof(int) * (*returnSize + 1));
        *((*result_ref) + *returnSize) = root->val;
        *returnSize = *returnSize + 1;
        inOrderTraversalHelper(root->right, returnSize, result_ref);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* result = NULL;
    // 直接为入参returnSize赋值，不需要额外malloc
    *returnSize = 0;
    if (root != NULL) {
        inOrderTraversalHelper(root, returnSize, &result);
    }
    return result;
}

内容的提问来源于stack exchange，提问作者Robert W