二叉树前序遍历递归代码疑问：成员变量为何能通过测试？

我用递归方法实现二叉树前序遍历，写出的代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root)
        {
            ans.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return ans;
    }
};

除测试用例[1,null,2,3]外，其余测试用例均能通过。但将vector<int> ans从函数内的局部变量改为类的成员变量后，该测试用例可得到正确输出，我想了解这一现象的原因。

问题根源分析 #

原代码的核心问题在于局部变量的作用域与递归调用的独立性：

• 每次调用preorderTraversal函数时，都会创建一个全新的局部ans向量。
• 以测试用例[1,null,2,3]为例：
  1. 首次调用处理根节点1，将1加入当前的ans，然后递归调用左子树（null，返回空向量），再递归调用右子树2。
  2. 递归处理右子树2时，会创建一个新的ans，将2加入其中，接着递归处理2的左子树3。
  3. 递归处理3时，又创建新的ans，将3加入其中。
• 这些递归调用中的ans都是独立的，最终返回的只是首次调用时创建的ans（仅包含1），自然无法得到正确结果[1,2,3]。

成员变量能解决问题的原因 #

当ans改为类的成员变量时：

• 成员变量属于Solution类的实例，所有递归调用共享同一个ans向量。
• 处理根节点1时，将1加入成员变量ans；递归左子树无操作；递归右子树2时，将2加入同一个ans；递归3时，再将3加入该ans。最终返回的就是完整的遍历结果。

更规范的递归写法（避免成员变量） #

使用辅助函数并通过引用传递ans，既能保证递归时共享同一个向量，又不会引入不必要的成员变量：

class Solution {
private:
    void traverse(TreeNode* root, vector<int>& ans) {
        if (!root) return;
        ans.push_back(root->val);
        traverse(root->left, ans);
        traverse(root->right, ans);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

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