迭代所有节点的总和 - 非递归 - 没有 'left' 和 'right'

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

但是，我很难弄清楚如何迭代地对所有节点求和。通常，对于定义中具有 'left' 和 'right' 的二叉树，我可以找到总和。但是，当我反复考虑这个定义时，这个定义让我有点困惑。

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

Answer 1

您可以迭代地创建一个列表、堆栈、队列或其他结构来容纳您运行通过的项目。把根放进去。开始遍历列表，获取一个元素并将其子元素也添加到列表中。将值添加到总和。取下一个元素并重复。这种方式没有递归，但性能和内存使用可能会更差。

Answer 2

如果我们谈论迭代，这是 queue.

的一个很好的用例

total = 0

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

print(total)
28

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

您可以使用 python 的原版列表模拟 stacks/queues。其他（更好的）替代方案是标准库中的 collections.deque 结构。我应该明确提到它的 enque/deque 操作比您对普通列表所期望的更有效。

Answer 3

回应第一个答案：

def sumNodes(root):
    current = [root]
    nodeList = []
    while current:
        next_level = []
        for n in current:
            nodeList.append(n.value)
            next_level.extend(n.children)
        current = next_level
    return sum(nodeList)

谢谢！这个解释帮助我更清楚地思考它。

迭代所有节点的总和 - 非递归 - 没有 'left' 和 'right'

Sum of all Nodes Iteratively - Not Recursively - Without 'left' and 'right'

python

iteration

algorithm

binary-tree