Сумма значений листьев бинарного дерева

Question

Я написал этот код, и когда я использую печать, я вижу, что я получаю листья. Тем не менее, окончательный результат от функции равен None, а не сумме листьев, которая в этом примере должна быть 7. Я был бы рад узнать, что здесь не так. Спасибо!

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val


def sum_leafs(tree):
    if tree is None:
        return 0

    if tree.right and tree.left:
        sum_leafs(tree.right)
        sum_leafs(tree.left)

    elif tree.right or tree.left:
        if tree.right:
            sum_leafs(tree.right)
        elif tree.left:
            sum_leafs(tree.left)

    elif tree.right is None and tree.left is None:
        return sum_leafs(tree.left) + 1


node = Node(10)
node.right = Node(2)
node.left = Node(11)
node.left.right = Node(5)

print(sum_leafs(node))

Answer 1

Вы забыли добавить + при суммировании ветвей (влево / вправо), а также забыли получить доступ к val, что является наиболее важным для всей работы.

Далее, логика может быть упрощена:

def sum_leafs(tree):
    if tree is None:
        return 0

    if not tree.right and not tree.left:
        return tree.val

    return sum_leafs(tree.right) + sum_leafs(tree.left)

Answer 2

Сначала я собираюсь обновить ваш Node интерфейс, чтобы можно было устанавливать left и right ветви при создании узлов -

class Node:
  def __init__(self, val=None, left=None, right=None):
    self.left = left
    self.right = right
    self.val = val

Это позволяет нам создавать тресс более эргономично, например -

t = Node(10, Node(11, None, Node(5)), Node(2))

Теперь мы напишем общую процедуру обхода.Это позволяет нам отделить 1) обход нашего дерева от 2) предполагаемой операции, которую мы хотим выполнить с каждым элементом дерева -

def traverse(tree):
  if tree is None:
    return
  else:
    yield tree.val
    yield from traverse(tree.left)
    yield from traverse(tree.right)

Теперь sum_leafs может быть простой программой.Ему больше не нужно заниматься обходом дерева, и вместо этого он может сосредоточиться на преобразовании линейной последовательности значений в требуемую сумму -

def sum_leafs(tree):
  r = 0
  for val in traverse(tree):
    r += val
  return r

print(sum_leafs(t))
# 28

Или вместо суммирования значений мы могли бы написать search функция, чтобы найти первое значение, которое передает предикат -

def search(test, tree):
  for val in traverse(tree):
    if test(val):
      return val

print(search(lambda x: x < 10, t))
# 5

print(search(lambda x: x > 99, t))
# None

Или, мы можем просто собрать каждое значение в список -

print(list(traverse(t)))
# [ 10, 11, 5, 2 ]

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

---

Если вам не нравятся генераторы, вы можете написать энергичную версию traverse, которая всегда возвращает list.Разница сейчас в том, что нет возможности частично пересечь дерево.Обратите внимание на сходство этой программы с версией генератора -

def traverse(tree):
  if tree is None:
    return [] # <-- empty
  else:
    return \
      [ tree.val
      , *traverse(tree.left)  # <-- yield from
      , *traverse(tree.right) # <-- yield from
      ]

print(traverse(t))
# [ 10, 11, 5, 2 ]

Answer 3

Вы не возвращаете правильно рассчитанные суммы листьев.Попробуйте это:

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val


def sum_leafs(tree):
    if tree is None:
        return 0

    elif tree.right and tree.left:
        return sum_leafs(tree.right) + sum_leafs(tree.left)

    elif tree.right or tree.left:
        if tree.right:
            return sum_leafs(tree.right)
        elif tree.left:
            return sum_leafs(tree.left)

    elif tree.right is None and tree.left is None:
        return tree.val

node = Node(10)
node.right = Node(2)
node.left = Node(11)
node.left.right = Node(5)

print(sum_leafs(node))

7

Answer 4

Вы не складываете суммы и не возвращаете их.Это также можно сделать с помощью метода в классе:

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val

    def sum(self):
        s = 0
        if self.left is not None:
            s += self.left.sum()
        if self.right is not None:
            s += self.right.sum()
        return self.val + s


node = Node(10)
node.right = Node(2)
node.left = Node(11)
node.left.right = Node(5)

print(node.sum())

возвращает:

28