push_back() 不是向向量中添加元素吗？ （C++ 树遍历）

Question

我正在解决一个树遍历问题，并使用 'push_back' 向量函数通过中序遍历更新一个向量。除了使用它，我还使用 cout 打印出要调试的解决方案。打印输出是正确的，但我的返回矢量与打印不匹配，所以我只能把它归结为我不了解 push_back 函数的工作原理。

这是我正在使用的功能：

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> order {};
        if (root != nullptr) {
            inorderTraversal(root->left);
            cout << "pushing back : " << root->val << std::endl; 
            order.push_back(root->val);
            inorderTraversal(root->right);
         } 
        
        return order;
    }

对于输入树 [1,null,2,3] 我的标准输出正在打印：

推回：1 推回：3 推回：2

这是正确的，但我返回的数组（顺序）只有 [1]。

Answer 1

您忽略了每次递归的结果。你应该这样做：

vector<int> inorderTraversal(TreeNode *root)
{
    vector<int> order;
    if (root != nullptr)
    {
        order = inorderTraversal(root->left);
        cout << "pushing back : " << root->val << std::endl;
        order.push_back(root->val);
        auto tmp = inorderTraversal(root->right);
        order.insert(order.end(), tmp.begin(), tmp.end());
    }

    return order;
}

---

更高效

就是说，如果您计算在此创建的局部向量的数量，虽然很短，但它们会很多（实际上与树中的节点一样多）。您可以通过在实际遍历和创建顺序向量之间提供垫片来消除所有这些 middle-men 向量：

void inorderTraversal_v(TreeNode const *root, std::vector<int>& order)
{
    if (root != nullptr)
    {
        inorderTraversal(root->left, order);
        order.push_back(root->val);
        inorderTraversal(root->right, order);
    }

    return order;
}

std::vector<int> inorderTraversal(TreeNode const *root)
{
    std::vector<int> order;
    inorderTraversal_v(root, order);
    return order;
}

这样做会创建一个向量，并在此过程中消除 (N-1) 个临时向量，其中 N 是树中的节点数。