我发现了leetcode的小bug

发表于2021-05-04更新于2021-05-04字数统计716阅读时长8分阅读次数

大家好，我是希达。

前言

今天，在用C语言刷LeetCode时，天真的我发现了leetcode的一个小 ”bug“。

但事实证明：。。。

正文

题目：二叉树的前序遍历

图片：

题目用C语言解答，我的解答如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
 //二叉树节点的个数
int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//前序遍历存值
void PrevTree(struct TreeNode* root,int *arr)
{
    static int i=0;
    if(root==NULL)
        return;
    arr[i++]=root->val;
    PrevTree(root->left,arr);
    PrevTree(root->right,arr);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    
    PrevTree(root,arr);
    return arr;
}

写好了代码，我习惯性的先执行代码，然后点击提交。

示例3：

执行代码：

提交：

好家伙！有一点被leetcode戏耍的感觉。

错误详情：堆溢出

我把测试用例“1”带入代码中，纸上计算，VS下调试。最后都没有发现问题。这里的堆怎么可能溢出呢？

于是，我又尝试点击了2次提交。

思考

老铁，你有发现我程序中的问题吗？

如果没有发现问题（像我一样觉得leetcode有bug），那么请尝试用多个测试用例调用该接口 。

再看看下面的原因。

百因必有果

我始终没有找到原因，随即请教了一位资深程序员老师。老师很快就发现了问题：静态局部变量

先来看一个简单的例子：

将test1和test2函数分别调用5次，结果是多少？

static静态局部变量

static静态局部变量是在堆区申请地址空间。在作用域结束时并不消失。当程序再次调用定义它的函数时，它保留了上一次留下来的值。

回到原问题中：

程序用一个测试用例来调用该函数并不会产生问题。前序遍历的函数只是执行了一次，并不会产生值的累加效果。但是如果程序多次调用该前序遍历函数，未免会产生错误。

可以看到leetcode已经调用了3次该接口。静态局部变量i发生了多次累加效果。以致于arr[i]超出了堆区的地址空间，越界访问，导致**堆溢出(heap-buffer-overflow)**，所以leetcode聪明的报出了bug。

leetcode真明智， 并没有bug！

结语

  1. 百因必有果，多从自身角度检查问题。
  2. 学会追根溯源，发现更深层次错误，多从不同方向思考问题。
  3. 多敲代码，多调试，多总结编码经验。

如果对文章有任何想法，欢迎在下方评论区留言。