所有节点的总和迭代 - 不递归 - 没有'左'和'右'

Question

我有这个二叉树结构:

# A Node is an object
# - value : Number
# - children : List of Nodes
class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

我可以很容易地递归地对节点求和:

def sumNodesRec(root):
    sumOfNodes = 0
    for child in root.children:
        sumOfNodes += sumNodesRec(child)
    return root.value + sumOfNodes 

示例树:

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

sumNodesRec(exampleTree)

> 28

但是,我很难弄清楚如何迭代地对所有节点求和.通常,使用定义中具有"左"和"右"的二叉树,我可以找到总和.但是,这个定义在迭代地思考它时会让我有点沮丧.

任何帮助或解释都会很棒.我试图确保我并不总是递归地做事情,所以我试图将正常的递归函数创建为迭代类型.

Answer 1

如果我们正在讨论迭代,这是队列的一个很好的用例.

total = 0

queue = [exampleTree]
while queue: 
    v = queue.pop(0)
    queue.extend(v.children)
    total += v.value

print(total)
28

这是一个常见的习语.迭代图遍历算法也以这种方式工作.

您可以使用python的vanilla列表模拟堆栈/队列.其他(更好的)替代方案是collections.deque标准库中的结构.我应该明确提到它的enque/deque操作比你对vanilla列表的期望更高效.