Função para encontrar o caminho mais longo em uma árvore binária

Python Hard functions

Tarefa «Função para encontrar o caminho mais longo em uma árvore binária»

Dada uma árvore binária, onde cada nó contém um número inteiro. É necessário encontrar a soma máxima dos valores em um caminho da raiz até a folha. O caminho deve começar na raiz e terminar em uma folha. Escreva a função max_path_sum(root), que recebe a raiz da árvore e retorna a soma máxima. A árvore é fornecida como uma lista, onde -1 indica a ausência de um nó. Restrições: número de nós não superior a 1000, valores dos nós de -1000 a 1000.

Formato de Entrada

Na primeira linha, um número inteiro n — o número de nós. Na segunda linha, n números inteiros separados por espaço — os valores dos nós na ordem de travessia em largura (nível por nível), onde -1 indica um nó vazio.

Formato de Saída

Um único número inteiro — a soma máxima no caminho da raiz até a folha.

Exemplos

Exemplo 1

ENTRADA

5
-1 2 3 -1 -1

SAÍDA

2

main.py