Сумма узлов в поддереве (не бинарная)

Question

В настоящее время я пытаюсь найти сумму всех узлов в указанном поддереве. Например, если у меня есть дерево

     A(5)
     / \
   B(5) C(6)
   /    /  \
  D(3) E(3) F(7)
            |
            G(1)

и я хочу узнать sum(C), который должен вернуть 17.

Это код, который я придумал, используя рекурсию, но Я не могу достичь поддерева, которое имеет более 2 уровней. Например, мой алгоритм, кажется, не достигает G. Я пытаюсь поправиться в рекурсии, но я не могу исправить это.

def navigate_tree(node,key): #node of the root of subtree, along with its key
    children = node.get_children()
    if (len(children) ==0):
        return node.key
    else:
        for child in children: #not a binary tree so trying to loop through siblings
            key += navigate_tree(child,key) #summing up key recursively
        return key 

Answer 1

Вам было бы лучше с улучшенным интерфейсом и возможностью использовать функции коллекций:

def navigate_tree(node): 
    children = node.get_children()
    key = node.key
    for child in children:
        key += navigate_tree(child)
    return key

# class Node and data A..G elided
print(navigate_tree(C))

Вывод:

17

Причина, по которой ваш код оказался не работа заключалась в том, что вы передавали предыдущий ключ на следующий уровень рекурсии. Тем не менее, ваш код, похоже, исправился. Если бы вы добавили немного print(node.key), вы бы увидели, что посещаете все правильные узлы.

Answer 2

Вы можете использовать рекурсию с sum:

class Node:
  def __init__(self, n, v, c=[]):
    self.name, self.val, self.children = n, v, c

def get_sum(node):
   return node.val+sum(map(get_sum, node.children))

tree = Node('A', 5, [Node('B', 5, [Node('D', 3)]), Node('C', 6, [Node('E', 3), Node('F', 7, [Node('G', 1)])])])
print(get_sum(tree.children[-1]))

Вывод:

17

Однако, если у вас нет доступа к точному узлу C, вы можете применить простой поиск как часть рекурсивной функции:

def get_sum(t, node):
  def inner_sum(d, s=False):
     return d.val*(s or d.name == t)+sum(inner_sum(i, s or d.name == t) for i in d.children)
  return inner_sum(node)

print(get_sum('C', tree))

Вывод:

17