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

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):
    if root is None:
        return 0
    return root.key + sum_of_nodes(root.childnodes[0]) + sum_of_nodes(root.childnodes[1])

Однако я получаю сообщение об ошибке:

Traceback (most recent call last):  
  File "D: /Documents/project1.py", line 170, in <module>  
  print (f'sum_of_nodes (exampleTree) => {sum_of_nodes (exampleTree)}') # 28  
  File "D: /Documents/project1.py", line 81, in sum_of_nodes  
  return root.value + sum_of_nodes (root.subnodes[0]) + sum_of_nodes (root.subnodes[1])  
  File "D: /Documents/project1.py", line 81, in sum_of_nodes  
  return root.value + sum_of_nodes (root.subnodes[0]) + sum_of_nodes (root.subnodes[1])  
IndexError: list index out of range

Answer 1

Вместо использования индексации для поиска дочерних узлов, вы можете использовать for l oop:

def sum_of_nodes(root):
  return root.key+sum(sum_of_nodes(i) for i in root.childnodes)

print(sum_of_nodes(testTree))

Вывод:

28

Answer 2

Вы можете использовать рекурсивный подход для суммирования узлов. Рекурсивный вызов происходит, только если узел не None. Добавьте значение текущего узла, затем проверьте, есть ли у него дочерние элементы. Если это так, выполните итерацию по каждому дочернему элементу, вызовите рекурсивный метод и добавьте полученный final_sum к текущему узлу final_sum. Каждый вызов функции имеет свое собственное значение final_sum, но вызов функции на узле root будет накапливать final_sum во всех дочерних узлах.

def get_sum(node):
    final_sum = 0
    if node is not None:
        final_sum += node.key
        if node.childnodes is not None:
            for child in node.childnodes:
                final_sum += get_sum(child)
    return final_sum