在遞歸函數的結果存儲/ BST

Question

我在寫這將在一定範圍內存儲的所有按鍵作爲一個字符串函數BST：

String rangeToString(TreeNode root,int low, int high, String result){ 
    if(root==null) return ""; 
    if(root.key>low)) rangeToString(root.leftChild, low, high,result); 
    if(root.key>=low && root.key.<=high) result+=root.key; 
    if(root.key<high) rangeToString(root.rightChild,low,high,result); 
    return result; 

}

我基本上做的在遍歷中，當它們在範圍內時向字符串添加值。 目前它返回一個只包含根密鑰的字符串。 我知道這個問題是在我的return語句，但我似乎無法得到如何實現功能沒有他們。 任何人都可以指向正確的方向嗎？

Answer 1

首先，你可能要包括你的遞歸調用返回，因爲你正在返回你的遞歸的結果：

String rangeToString(TreeNode root,int low, int high, String result){ 
    if(root==null) return ""; 
    if(root.key>low)) return rangeToString(root.leftChild, low, high,result); 
    if(root.key>=low && root.key.<=high) result+=root.key; 
    if(root.key<high) return rangeToString(root.rightChild,low,high,result); 
    return result; 
} 

我懷疑你的條件，所以我會花一些時間研究這些......事實上，遞歸的回報正在假設你的條件結構。

而且，聚會參數一個方式是很直觀的方法是使用尾遞歸和您的參數積累的結果。

你可以在這裏閱讀更多： http://en.wikipedia.org/wiki/Tail_call

的關鍵是，您使用的參數本身聚集的結果，而當你的函數完成後，你回到你的參數（即累積的結果的那些） 。

Answer 2

你可以傳遞到你的參數的supplentary「積累到現在」的字符串列表（說你的名字curlist）。那麼當你返回你回到這個curlist argument + .Add(your found key for this recursion level)，並在地方，你遞歸調用fonction（rangeToString）您連接結果到當前列表curlist（使用追加或其他）。

僞代碼：

list<string> myRecursiveFunc(some args, list<string> curlist) 
{ 
    if (recursConditionOK) 
     curlist = curlist.Append(myRecusriveFunc, curlist); 
    return curlist; 
}