递归：按顺序遍历返回列表

Question

我有一个基础函数，在C++中执行中序遍历：

void inorder(Node *root)
{
    if(root != NULL)
    {
       inorder(root->left);
       cout<<root->data<<endl;
       inorder(root->right);
    }
}

然而，我希望将遍历结果返回为一个列表。但关键问题是我们如何确定递归函数何时结束以便返回列表。以下是我目前完成的代码：

vector<int> inorder(Node *root, vector<int> listToAdd)
{
    if(root != NULL)
    {
       inorder(root->left, listToAdd);
       listToAdd.push_back(root->data);
       inorder(root->right, listToAdd);

       //return here?
    }
    // return here?
}

我认为这个问题的答案也会帮助我理解递归的核心概念。

- Ali

Answer 1

关键是如何确定这个递归函数什么时候结束

与普通函数一样，递归函数在顶层调用返回时结束。您的函数存在问题，它尝试同时构造列表和返回列表，应该只做其中之一。

构建列表很简单-将函数改为 void，并进行以下更改：

void inorder(Node *root, vector<int>& listToAdd)
{
    if(root != NULL)
    {
       inorder(root->left, listToAdd);
       listToAdd.push_back(root->data);
       inorder(root->right, listToAdd);
    }
}

就是这样！我所做的两个更改是通过引用传递参数，然后返回void。按照以下方式调用您的函数：

vector<int> inorderList;
inorder(myNode, inorderList);

如果您想返回列表，您可以按以下方式修改函数：

list<int> inorder(Node *node) {
    if (root != NULL) {
        list<int> lhs = inorder(node->left);
        list<int> rhs = inorder(node->right);
        copy(rhs.begin(), rhs.end(), back_insert_iterator<list<int> >(lhs));
        return lhs;
    } else {
        return list<int>();
    }
}

请注意，第二种选择需要更多的复制。

- Sergey Kalinichenko

Answer 2

如果您将返回语句放在 if 的主体内，则在 root 为空的情况下不会触发返回语句。这似乎很糟糕。现在，请考虑将 return 放在函数的末尾（条件外）。现在，无论 root 是否为空，都将到达 return，这是您想要的。

也就是说，您应该考虑当您进行这两个递归调用时会发生什么。您是否依赖于递归调用返回一个具有另一个项目的 vector<int>？如果是这样，那么您应该考虑获取从调用 inorder 返回的值并对其执行某些操作，而不仅仅是忽略它。希望这能帮到您。

- tuckermi