Максимальная сумма узлов в каждом пути в бинарном дереве


Я хотел сделать обзор на алгоритм, я написал для двоичного дерева. Проблема заключается в следующем.

Вернуть максимальную сумму между всеми ветвями в двоичное дерево. Филиал определяется как все пути от корня до листьев.

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

#branch one
root = Node(10)

second = Node(5)
root.left = second

third = Node(1)
second.left = third

fourth = Node(3)
third.left = fourth

tenth = Node(5)
third.right = tenth

fifth = Node(20)
root.right = fifth

sixth = Node(60)
fifth.left = sixth

seventh = Node(3)
fifth.right = seventh

nineth = Node(40)
seventh.right = nineth


def find_max_sum_of_binary_tree_path(root):
    curr_list = []
    curr_max = [0]

    def binary_tree_recurse(node):
        if node:
            if not node.left and not node.right:
                curr_list.append(node.value)
                list_sum = sum(curr_list)
                if list_sum > curr_max[0]:
                    curr_max[0] = list_sum
                curr_list.pop()

            curr_list.append(node.value)
            binary_tree_recurse(node.left)
            binary_tree_recurse(node.right)
            curr_list.pop()

    binary_tree_recurse(root)
    return curr_max[0]

  #      10
  #      / \
  #     5   20
  #    /   / \
  #   1   60   3
  #  / \       \
  # 3   5       40

find_max_sum_of_binary_tree_path(root) #should return 90 based on my tree
>90

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



589
4
задан 14 марта 2018 в 12:03 Источник Поделиться
Комментарии
1 ответ

Кажется, вы делаете слишком много работы.

Максимальная сумма одного узла, который не будет 0.

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

Что только рекурсии должно быть достаточно, чтобы избежать с использованием промежуточных структур данных. Что-то вроде:

def find_max_sum_of_binary_tree_path(root):
if root is None:
return 0

left_sum = find_max_sum_of_binary_tree_path(root.left)
right_sum = find_max_sum_of_binary_tree_path(root.right)

return root.value + max((left_sum, right_sum))

4
ответ дан 14 марта 2018 в 12:03 Источник Поделиться