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

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

关键是我们如何确定这个递归函数何时实际结束

与普通函数一样,递归函数在其调用的最高级返回时立即结束.你的函数的问题是它试图构造一个列表,并返回它; 它应该做一个或另一个.

构建列表很简单 - 创建函数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>();
    }
}

请注意,第二种选择需要更多复制.