У меня проблемы с реализацией рекурсии в этой задаче

Question

Я имею дело с бинарными деревьями. У меня есть class Tree, и я хочу написать метод sum(), который возвращает сумму всех чисел в дереве. Вот что я написал:

def sum(self):
    s = self.n
    if self.left == None and self.right == None:
        return
    elif self.left == None and self.right != None:
        s = s + self.right.sum()
    elif self.left != None and self.right == None:
        s = s + self.left.sum()
    else:
        s = s + self.right.sum()
        s = s + self.left.sum()
    return s

Но это не работает, и я застрял здесь. Как мне реализовать рекурсию в этой задаче?

Answer 1

Ваш код не работает, потому что в вашем начальном return отсутствует значение.

Кроме того, ваша функция содержит много избыточности, которую можно удалить, в результате чего мы получим:

def sum(self):
    s = self.n
    if self.right != None:
        s += self.right.sum()
    if self.left != None:
        s += self.left.sum()
    return s