不要理解有关C＆＃x2B;＆＃x2B;

Question

因此，我正在做这个leetcode问题，不了解发生了什么。这是关于通过二进制树的预订遍历。

问题的问题

起初，我认为实现我在中学到的遍历代码非常简单班级。

    vector<int> preorderTraversal(TreeNode* root) {
    vector<int> final;

    if(root == nullptr){
        return final;
    }

    final.push_back(root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);

    return final;
}

但是后来，当代码在其中一个测试用例中，我碰到了一个障碍。

我挠头递归地绕过这个问题，直到我查看了发布的一些解决方案。

    vector<int>ar1;
void preOrder(TreeNode *root)
{
    if(root==nullptr)
        return;
    ar1.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}
vector<int> preorderTraversal(TreeNode* root) 
{
    preOrder(root);
    return ar1;
}

我的问题是，是什么使他们的遍历使用与在第一个代码段中进行的方法不同的方法？

Answer 1

评论代码：

矢量最终；是从返回从未恢复过的函数的局部变量，只是掉入深渊。如果第二个解决方案使用全局变化来捕获它，则两者都很漂亮，我个人通过Treenode通过参考向量，

但是如果您想以自己的方式进行操作，那么您会做这样的事情（不是使用IDE/编译器，可能需要一些修复程序）

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> final;

    if(root == nullptr){
        return final;
    }

    final.push_back(root->val);
    auto leftVec = preorderTraversal(root->left);
    if(!leftVec.isEmpty(){
       final.reserve(final.size() + leftVec.size());
       final.insert(std::end(final), std::begin(leftVec ), std::end(leftVec ));
    }

    auto rightVec = preorderTraversal(root->right);
    if(!rightVec.isEmpty(){
       final.reserve(final.size() + rightVec .size());
       final.insert(std::end(final), std::begin(rightVec ), std::end(rightVec ));
    }

    return final;
}

建议的更改，请看到它的好多了？

另外，如果您知道treenode上有多少个节点，那么如果您不希望代码制作一百万个不必要的副本，则要保留全尺寸。

void preorderTraversal(TreeNode* root, vector<int>& output) {
    if(root == nullptr){
        return;
    }
    
    //Should use emplace back to remove a copy here too
    output.emplace_back(root->val);
    preorderTraversal(root->left, output);
    preorderTraversal(root->right, output);
}