如何將此遞歸函數轉換爲迭代函數？

Question

F = function(node){ 
    return typeof(node)!="object" ? 
       node 
      : transformable([F(node[0]),F(node[1])]) ? 
       F(transform(F(node[0]),F(node[1]))) 
      : node; 
}; 

該函數接收二叉樹，如[1,[[2,3],[4,5]]]，並遞歸應用一系列變換。有沒有辦法將該函數轉換爲：

1. 它取而代之的是一個扁平二叉樹，如[N,1,N,N,2,3,N,4,5];
2. 它不使用遞歸？

Answer 1

這取決於你的意思是迭代。如果你的意思是用循環來解決這個問題，那麼你可能需要一個回溯堆棧，這樣可以在當前的遞歸實現中調用堆棧，所以實際上它仍然是遞歸的，只有不同的堆棧。

如果你不分支，你只能做沒有堆棧的純粹迭代的東西。即每個尾部只有一個遞歸調用。樹有兩個或更多，因此它們只能被遞歸處理。