递归中static vector与global vector实现中序遍历提交失败原因问询

你给出的第一版使用全局vector的代码：

vector<int> r;
vector<int> inorderTraversal(TreeNode* root) {
    if(root==NULL)
        return r;
    inorderTraversal(root->left);
    r.push_back(root->val);
    inorderTraversal(root->right);
    return r;
}

你遇到问题的第二版使用静态vector的代码：

vector<int> inorderTraversal(TreeNode* root) {
    static vector<int> r;
    if(root==NULL)
        return r;
    inorderTraversal(root->left);
    r.push_back(root->val);
    inorderTraversal(root->right);
    return r;
}

核心原因 #

• static修饰的函数内部局部变量，存储在程序的静态存储区，生命周期和整个程序进程完全一致，仅会在函数第一次被调用时执行一次初始化，后续所有函数调用都会复用该变量的现存值，不会重新初始化。
• 在线判题系统的运行逻辑是在同一个进程内依次调用你的函数执行所有测试用例，不会每执行一个测试用例就重启进程。

问题复现逻辑 #

1. 执行第一个测试用例时，r第一次被初始化为空vector，遍历完成后存储了第一个用例的正确结果，单测通过。
2. 执行第二个测试用例时，r不会清空，还保留着第一个测试用例的结果：
   • 如果当前测试用例是空树，函数直接返回r，得到的就是上一个测试用例的输出，自然不符合预期。
   • 如果当前测试用例是非空树，会在已有结果的基础上追加当前树的遍历值，最终返回的是多个测试用例结果的累加值，同样无法通过测试。

单独运行单个测试用例时可以得到正确结果，是因为单次运行程序只会调用一次函数，r只会初始化一次且没有历史残留值，问题不会暴露。

修复建议 #

不要使用静态或者全局变量存储遍历结果，推荐改为用辅助函数传递vector引用的方式实现，示例如下：

void traversal(TreeNode* root, vector<int>& res) {
    if (root == nullptr) return;
    traversal(root->left, res);
    res.push_back(root->val);
    traversal(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    traversal(root, res);
    return res;
}

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