Алго ошибка

Question

Написал неоправданно сложное решение следующего вопроса:

Учитывая двоичное дерево и сумму, определите, есть ли у дерева путь от корня к листу так, чтобы сложить все значения вдольпуть равен заданной сумме.

В любом случае, я пытаюсь отладить то, что пошло не так.Я использовал именованный кортеж, чтобы я мог отслеживать, было ли найдено число и текущую сумму, но похоже, что текущая сумма никогда не увеличивается больше нуля.Однако на любом данном листовом узле промежуточная сумма будет значением конечного узла, и на следующей итерации текущая сумма должна быть увеличена на текущую промежуточную сумму.Кто-нибудь знает, что не так с моим "рекурсивным прыжком веры" здесь?

def root_to_leaf(target_sum, tree):
    NodeData = collections.namedtuple('NodeData', ['running_sum', 'num_found'])

    def root_to_leaf_helper(node, node_data):
        if not node:
            return NodeData(0, False)

        if node_data.num_found:
            return NodeData(target_sum, True)

        left_check = root_to_leaf_helper(node.left, node_data)
        if left_check.num_found:
            return NodeData(target_sum, True)

        right_check = root_to_leaf_helper(node.right, node_data)
        if right_check.num_found:
            return NodeData(target_sum, True)

        new_running_sum = node.val + node_data.running_sum 
        return NodeData(new_running_sum, new_running_sum == target_sum)

    return root_to_leaf_helper(tree, NodeData(0, False)).num_found

РЕДАКТИРОВАТЬ: я понимаю, что на самом деле это просто проверка, имеет ли какой-либо путь (не заканчивающийся на листе) правильное значение, но мой вопрос по-прежнему заключается в понимании того, почему промежуточная сумма не увеличивается должным образом.

Answer 1

Я думаю, вам нужно четко подумать о том, течет ли информация по дереву (от корня к листу) или вверх по дереву (от листа к корню).Похоже, что аргумент node_data для root_to_leaf_helper инициализируется в верхней части дерева, корня, а затем передается через каждый узел через рекурсивные вызовы.Это нормально, но, насколько я могу судить, это никогда не меняется на пути вниз по дереву.Это просто прошло нетронутым.Поэтому первая проверка для node_data.num_found всегда будет ложной.

Еще хуже, поскольку node_data всегда одинаков ((0, False)) на пути вниз по дереву, следующая строка, которая пытаетсядобавьте текущее значение узла к текущей сумме:

new_running_sum = node.val + node_data.running_sum 

всегда будет прибавлять node.val к 0, поскольку node_data.running_sum всегда равно 0.

Надеюсь, это понятно, я понимаючто это немного сложно объяснить.

Но попытка очень четко подумать об информации, протекающей по дереву (в аргументах рекурсивных вызовов), по сравнению с информацией, протекающей по дереву (в возвращаемом значении рекурсивных вызовов)сделаю это немного более понятным.

Answer 2

Вы можете сохранить текущий список пути как часть сигнатуры рекурсивной функции / метода и вызывать функцию / метод на правом и левом узлах с помощью генератора.Генератор позволит вам найти пути, идущие от начальных узлов.Для простоты я реализовал решение как метод класса:

class Tree:
  def __init__(self, *args):
    self.__dict__ = dict(zip(['value', 'left', 'right'], args))
  def get_sums(self, current = []):
    if self.left is None:
      yield current + [self.value]
    else:
      yield from self.left.get_sums(current+[self.value])
    if self.right is None:
      yield current+[self.value]
    else:
      yield from self.right.get_sums(current+[self.value])

tree = Tree(4, Tree(10, Tree(4, Tree(7, None, None), Tree(6, None, None)), Tree(12, None, None)), Tree(5, Tree(6, None, Tree(11, None, None)), None))
paths = list(tree.get_sums())
new_paths = [a for i, a in enumerate(paths) if a not in paths[:i]]
final_path = [i for i in paths if sum(i) == 15]

Вывод:

[[4, 5, 6]]