如何将这个递归函数转换为迭代函数

How to transform this recursive function into an iterative one?

本文关键字：转换 迭代 函数 递归函数      更新时间：2024-06-22
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. 它不使用递归？

这取决于你所说的迭代是什么意思。如果你的意思是用循环来解决它，这是可能的，但你需要一个回溯堆栈，它几乎可以镜像你在当前的递归实现中调用堆栈，所以在实践中它仍然是递归，只是使用不同的堆栈。

如果你不分支，你只能做没有堆栈的纯迭代东西。 即每个尾巴只有一个递归调用。树有两个或更多，因此只能递归处理。

相关文章：