二叉树的预序遍历

Question

Ques-给定二叉树的根，返回其节点值的预序遍历。链接此处

我正在用递归方法来解决这个问题。下面给出的是我的代码

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root)
{
ans.push_back( root -> val);
preorderTraversal(root ->left);
preorderTraversal(root ->right);
}
return ans;
}
};

除了一个测试用例，即[1，null，2,3]，所有测试用例都通过了。但是当我在vector<int> preorderTraversal(TreeNode* root)之前声明vector<int> ans时，测试用例会给出正确的输出。我想知道为什么会发生这种事。

Answer 1

ans变量在函数调用之间不共享，并且您会丢弃递归的结果，因此您最多可以向结果添加一个元素。

授权给助手功能是避免复制和手动状态管理的常见解决方案：

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
private:
void traverse(const TreeNode* root, vector<int>& ans) const
{
if(root)
{
ans.push_back(root->val);
traverse(root->left, ans);
traverse(root->right, ans);
}
}
};

Answer 2

vector<int> ans;是一个局部变量，在调用preorderTraversal后被销毁。除此之外，您还将忽略递归调用的返回值。我认为您希望将ans保留为类字段，并使用递归调用填充它：

class Solution {
public:
void preorderTraversal(TreeNode* root) {
if(root)
{
_ans.push_back( root -> val);
preorderTraversal(root ->left);
preorderTraversal(root ->right);
}
}
private:
std::vector<int> _ans;
};

当然，你需要一些访问者，一种清除结果的方法，等等。但我想这不是你问题的范围。

Answer 3

问题是忽略了对preorderTraversal的递归调用的返回值。因此，您的方法将返回最大值1，即root节点的值。

当前代码的一个简单解决方案是将重新调用的结果存储在一个变量中，并将元素附加到ans:

ans.push_back( root -> val);
auto l = preorderTraversal(root ->left);
ans.insert(ans.end(), l.begin(), l.end());
auto r = preorderTraversal(root ->right);
ans.insert(ans.end(), r.begin(), r.end());

由于递归调用中的向量是有效复制的，所以效率不高。

一种更有效的方法是通过引用preorderTraversal来传递结果vector(在为根调用它之前，它应该被创建为空)。则preorderTraversal可以将元素(包括递归)添加到该结果vector。

通过引用传递结果的另一种方法是将其存储在类的成员变量中，如另一个答案所示。