創建一個迭代函數，而不是遞歸python

Question

def sum(root): 
    if root.children == []: 
     return root.value 
    else: 
     temp = 0 
     for n in root.children: 
      temp += sum(n) 
     temp+= root.value 
    return temp 

我得到我的函數遞歸工作，並試圖找出一個簡單的方法來迭代。我只是試圖找到指導，如果我會使用一個while循環或什麼。

Answer 1

使用隊列或堆棧;從隊列或堆棧中取一個元素，將值添加到正在運行的總數中，將所有子元素添加到隊列或堆棧中，然後處理下一個元素。使用while循環，當您的隊列或堆棧爲空時結束。

堆棧和隊列之間的唯一區別是，您將先處理元素深度（堆棧）或先呼吸（隊列）。

你的遞歸代碼是深度優先，所以要反覆地重複相同的行爲，使用堆棧：

def sum_nodes_iteratively(root): 
    elements = [root] 
    total = 0 
    while elements: 
     element = elements.pop() 
     elements.extend(element.children) 
     total += element.value 
    return total 

演示：

>>> class Node(object): 
...  def __init__(self, value, children): 
...   self.value = value 
...   self.children = children 
... 
>>> def sum_nodes_iteratively(root): 
...  elements = [root] 
...  total = 0 
...  while elements: 
...   element = elements.pop() 
...   elements.extend(element.children) 
...   total += element.value 
...  return total 
... 
>>> sum_nodes_iteratively(Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])) 
28