LeetCode 94二叉树中序遍历：二级指针传递异常问题排查

问题场景 #

在实现二叉树中序遍历的代码时，发现调用helper函数时传入&cpy程序能正常运行，但传入&gResult却无法得到正确结果，错误表现为返回的数组内容不符合预期，无法正确获取中序遍历结果。

相关代码 #

int countNode(struct TreeNode* root)
{
    if(root)
        return 1 + countNode(root->left) + countNode(root->right);
    return 0;
}

void helper(struct TreeNode* root, int** res)
{
    if(root)
    {
        helper(root->left, res);
        *((*res)++) = root->val;
        helper(root->right, res);
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *gResult = NULL; 
    *returnSize = countNode(root);
    gResult = (int*)malloc(((*returnSize)) * sizeof(int));
    memset(gResult, 0, (*returnSize) * sizeof(int));   
    int *cpy = gResult;
//    helper(root, &cpy);
    helper(root, &gResult);
    return gResult;
}

问题原因 #

核心问题出在helper函数里的*((*res)++) = root->val;这行代码：

• 这行代码会通过二级指针res拿到指向数组的指针，把当前节点值赋值到指针指向的位置后，直接让这个指针本身向后移动一位。
• 传入&cpy时，cpy是gResult的副本，helper修改的是cpy的指向，gResult始终保持指向malloc分配的数组起始地址，最后返回gResult就能拿到完整的遍历结果。
• 但如果传入&gResult，helper会直接修改gResult本身的指向，遍历完成后gResult已经移动到数组末尾（甚至超出数组范围），此时返回gResult，调用者拿到的是指向无效区域的指针，自然无法读取正确数据。

解决办法 #

保持使用cpy这个副本指针传入helper，或者在调用helper前先保存gResult的起始地址，遍历结束后返回该起始地址。

内容的提问来源于stack exchange，提问作者Kingkong Jnr