c++ - 访问类中的成员向量和访问在另一个成员函数中创建的向量有什么区别？

Question

我试图解决 Leetcode 问题589 “N-ary Tree Preorder Traversal”。我有两个具有相同逻辑的实现，如下所示：第一个是尝试访问类中的成员向量：

class sth {
public:
  vector<int> nums;
  vector<int>
  preorder(Node *root) {
    if(!root)
      return nums;
    nums.push_back(root->val);
    for(auto i : root->children)
      preorder(i);
    return nums;
  }
}

第二个是尝试访问在另一个成员函数中创建的向量。

class sth {
public:
  void
  tracking(Node *root, vector<int> &nums) {
    if(!root)
      return;
    nums.push_back(root->val);
    for(auto i : root->children) {
      tracking(i, nums);
    }
    return;
  }
  vector<int>
  preorder(Node *root) {
    vector<int> nums;
    tracking(root, nums);
    return nums;
  }
}

我不知道这两种实现之间的区别。他们试图描述相同的逻辑，但是时间和空间的复杂性有很大的不同。

标签： c++class

Answer 1

在第一个实现中，每个preorder调用都按值返回一个向量。这意味着对于您访问的每个节点，您都在复制您在该点之前构建的向量。此外，由于向量是sth对象状态的一部分，因此第二次调用preorder将重用已包含数据的同一向量。

在第二个实现中，您只在返回向量时复制一次向量（或者根本不复制，因为可以省略副本）。而且由于没有外部状态，重复调用preorder将返回相同的内容。