Как найти сумму узлов в дереве без рекурсии

Question

Я пытался решить эту проблему несколькими разными способами.

Узел для моего кода определен следующим образом: Узел - это объект
- значение: Число
- потомки: список узлов

class Node:
    def __init__(self, key, childnodes):
        self.key = key
        self.childnodes = childnodes

    def __repr__(self):
        return f'Node({self.key!r}, {self.childnodes!r})'


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

Я подошел близко чтобы решить проблему с кодом:

def sum_of_nodes(root):
    sum = 0

    while root:
        sum += root.key
        print(sum)
        root = root.childnodes
        print(root)
        root = root.pop()
        print(root)

print(sum)

Однако он пропускает некоторые части кода, и я не уверен, как go исправить его. Результат приведенного выше кода:

1
[Node(2, []), Node(3, [Node(4, [Node(5, []), Node(6, [Node(7, [])])])])]
Node(3, [Node(4, [Node(5, []), Node(6, [Node(7, [])])])])
4
[Node(4, [Node(5, []), Node(6, [Node(7, [])])])]
Node(4, [Node(5, []), Node(6, [Node(7, [])])])
8
[Node(5, []), Node(6, [Node(7, [])])]
Node(6, [Node(7, [])])
14
[Node(7, [])]
Node(7, [])
21
[]

Наряду с ошибкой:

Traceback (most recent call last):
  File "D:/Documents/project1.py", line 191, in <module>
    print(f'itersum_of_nodes(testTree) => {itersum_of_nodes(testTree)}')  # 28
  File "D:/Documents/project1.py", line 108, in sum_of_nodes
    root = root.pop()
IndexError: pop from empty list

Я также попробовал метод, которому научили в geeksforgeeks.org/inorder-tree-traversal- без рекурсии /, однако, мои дочерние узлы определяются как список, а не .right или .left, и я не уверен, как из-за этого получить нужную мне информацию. Код:

stack = []
    sum = 0
    current = root

    while True:
        if current.childnodes[0] is not None:
            stack.append(current)
            current = current.childnodes[0]
        elif stack:
            current = stack.pop()
            sum += current.value
            current = current.childnodes[1]
        else:
            break

Answer 1

Вот рабочая версия while l oop, которая пересекает ваше дерево без рекурсии. Основная проблема в том, что ваши узлы хранят дочерние элементы не по отдельности, а в виде списка. Это означает, что вам нужно быть бдительным, проверяя, сколько детей на самом деле имеет узел.

def sum_of_nodes(root):
    sum = 0
    stack = []

    # While the current node is not none
    while root:
        # Add the value of the current node to the sum
        sum += root.key
        # Check if the current node has children
        if root.childnodes:
            # If it has two children, append the second child to the stack
            if len(root.childnodes) == 2:
                stack.append(root.childnodes[1])
            # Set the first child as the current node
            root = root.childnodes[0]
        # If the current node doesn't have any children, take one from the stack
        elif stack:
            root = stack.pop()
        # If we run out of children in the stack, end the while loop
        else:
            break        
    return sum