c++ - 递归:按顺序遍历返回列表

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

我认为这个问题的答案也有助于我了解递归的核心概念

Answer 1

The key thing is how can we determine when this recursive function actually ends

与普通函数一样，递归函数在其调用的顶层返回后立即结束。您的函数的问题在于它试图同时构造一个列表并返回它；它应该做一个或另一个。

构造列表很简单 - 使您的函数无效，并按如下方式更改它:

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

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