二叉树中序遍历习题引发的时间空间复杂度思考：内存角度

今天做了一道简单的二叉树遍历。

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

先来看我写的代码：

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

官方的代码：

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

是不是看起来我的代码好简洁，是吧？可是我发现了一个问题，我的时间空间复杂度都不如官方代码，尤其是时间复杂度：

我的代码的用时：

我就在想问题出在哪？
细心的朋友可以看出两个不同之处：
官方的代码是把容器以形参的方式传入到函数中。
有什么作用？

可以看到，递归的代码在内存中会复制多份，里面的容器也会频繁使用。当函数传入参数，内存就不会频繁去找这个容器所在的地址，直接拿来就可以使用。而且函数中 容器 是以引用的形式传入，函数中只会有一个容器的副本，并没有完全copy。