不明白这个关于二叉树遍历的概念C++

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

但是当代码在一个测试用例中击中根的左子节点中的NULL时，我遇到了一个障碍。

我不知道如何递归地绕过这个问题，直到我看到了一些张贴的解决方案。

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