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;
}

---

更高效

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

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 是树中的节点数。