使用隊列或堆棧;從隊列或堆棧中取一個元素,將值添加到正在運行的總數中,將所有子元素添加到隊列或堆棧中,然後處理下一個元素。使用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
我會建議尋找到廣度優先搜索。一般來說,您想要迭代地執行深度優先搜索和廣度優先搜索。 –
遍歷樹是遞歸解決方案迄今最簡單的一種情況。反覆做這樣做會複雜得多,因爲沒有任何好處。 – jasonharper