7

I have a basic function that does an in order traversal in C++: 

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

However, I would like to return a list as a result of this in order traversal. But the key thing is how can we determine when this recursive function actually ends and I can return the list. Here is the code that I've done so far;

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

I think the answer of this question would also help me with the core concept of recursion as well

4

2 回答 2

10

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

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

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

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

于 2013-07-15T19:11:53.060 回答
0

如果将 return 语句放在 if 的主体中，那么在 root 为 null 的情况下，您不会遇到 return 语句。这似乎很糟糕。现在，想想如果将 return 放在函数的末尾（条件之外）会发生什么。现在，无论 root 是否为 null，都将达到 return，这就是你想要的。

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

于 2013-07-15T19:17:00.777 回答