Python - Расчет суммы ветви Бинарного Дерева - PullRequest
Новая
       8

Python - Расчет суммы ветви Бинарного Дерева

2 голосов
/ 13 февраля 2020

Итак, я решаю проблему algoExpert.io. Вопрос в том, чтобы написать алгоритм для вычисления всех сумм ветвлений слева направо. Проблема заключается в том, что тесты проходят в зависимости от того, как я вызываю вспомогательную функцию, и я действительно не могу найти, почему. хорошо, как видно из этой картины. enter image description here

Но как только я это сделаю (это было мое первоначальное решение): 

def branchSums(root): 
    return branchHelper(root) # Fail

enter image description here

Почему при использовании сумм по умолчанию = [] происходит сбой таким образом?

enter image description here

Это сообщение об ошибке. Я вижу, что в тестовом примере использовался root 1 и оставался дочерний элемент 3. И мой код выплевывал [1, 3], когда я использую второй метод.

Я действительно не могу понять это, любая помощь будет оценена.

1 Ответ

1 голос
/ 13 февраля 2020

Это из-за того, что ваши вторые параметры сумм имеют значение по умолчанию.

Если вы перезапишете его следующим, вы пройдете тест 

def branchHelper(root, sums=None, branchSum=0):
    if root is None:
        return

    if sums is None:
        sums = []

    branchSum += root.value
    if root.left is None and root.right is None:
        sums.append(branchSum)
    branchHelper(root.left, sums, branchSum)
    branchHelper(root.right, sums, branchSum)
    return sums

Пример, почему это неправильно: 

def wrong_func(append_item, items=[]):
    items.append(append_item)
    return items

wrong_func(1) # output [1]
wrong_func(2) # output [1, 2]


def correct_func(append_item, items=None):
    if items is None:
        items = []
    items.append(append_item)
    return items

correct_func(1) # output [1]
correct_func(2) # output [2]

При первом вызове функции python создает постоянный список. Каждый последующий вызов append добавляет значение в этот исходный список. Вот что происходит, когда algoExpert.io проверяет ваш код.

И именно поэтому первый тест пройден, а второй не пройден (первое тестовое двоичное дерево с одним элементом 1, второй тест выполняет следующую проверку с 1, 2 и добавляет новый значение в вашем списке sums, и вы получили неудачный тест.

...