遞歸：中序遍歷返回一個列表

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

注意，第二個選擇需要更多的複製。

Answer 2

如果將return語句放在if的正文中，那麼在root爲null的情況下，您不會碰到return語句。這看起來很糟糕。現在，想想如果將返回放在函數的末尾（條件之外），會發生什麼情況。現在，無論root是否爲null，都將返回返回值，這正是您想要的。

這就是說，你應該考慮一下當你進行這兩個遞歸調用時會發生什麼。你是否依靠遞歸調用返回一個vector<int>現在有另一個項目？如果是這樣，那麼你應該把電話號碼返回的值作爲inorder，並用它做一些事情，而不是忽略它。希望有所幫助。