Challenge: Given a *non-empty* binary tree, find the maximum path sum. Para este problema, um caminho é definido como qualquer sequência de nós de algum nó inicial para qualquer nó na árvore ao longo das conexões pai-filho. O caminho deve conter pelo menos um de nós e não precisamos ir até a raiz:

Example #1:
Input: 
4
/ \
5 6
Output: 15

Exemplo 2:

Input: 
-10
/ \
9 20
/ \
15 7
Output: 42

O Desafio

Como o nome indica, uma árvore binária é um tipo popular de árvore baseada em estrutura de dados. Para apoiar a sua eficiência de tempo e espaço, as árvores são muitas vezes representadas por uma chave e dois ou mais nós de folhas, semelhantes às seguintes estruturas:

As one may guess, recursion is also a common property of tree-based structures. Embora a maioria das funções recursivas são malvistos em aplicações reais, árvores permitem que certas eficiências de cada folha de nó também pode representar outra árvore:

Se não entendeu corretamente, árvores pode levar a uma confusão bem como uma maior complexidade. Para resolver o nosso desafio de código, precisamos de criar um método consistente para navegar na nossa árvore e uma forma de comparar todas as possíveis permutações.

vamos trabalhar visualizando nossas idéias antes de comprometê-las com o código. Para começar, vamos primeiro abordar como navegar a árvore. Uma vez que estruturas baseadas em árvores incorporam uma propriedade de conceito adicional de * profundidade*, técnicas simples como a enumeração rápida não são normalmente aplicadas. Em vez disso, podemos usar algoritmos transversais específicos como profundidade ou largura-primeira Busca (por exemplo, DFS e BFS respectivamente). Mesmo que o tópico de BFS seja detalhado o suficiente para uma nova discussão, podemos concluir que esta seria a maneira normal de atravessar tal estrutura. No entanto, uma vez que estamos trabalhando com uma árvore binária, podemos aplicar eficiências algorítmicas específicas para ajudar a encurtar o processo transversal.o que é uma árvore binária? Essencialmente, é uma matriz padrão que é visualizada como uma árvore. Neste caso, a ênfase é colocada nos aspectos de visualização, uma vez que isso afetará a forma como navegamos a estrutura. Por exemplo, para cada nó, seus nós filhos da folha esquerda e direita podem ser calculados usando estas fórmulas simples:

Como discutido, estas fórmulas funcionam porque a estrutura subjacente para nossa árvore é uma matriz. Isto difere de outras estruturas como uma árvore B, Trie ou grafo onde se aplicaria uma estrutura de dados personalizada específica para representar um modelo.

fazendo comparações

Uma Vez Que nossa árvore binária não é nada mais do que uma matriz, podemos realmente usar a enumeração básica para iterar através de todos os valores. No entanto, vamos aplicar as nossas fórmulas para determinar os nós de folhas infantis. Uma vez estabelecido, podemos rastrear os totais de cada sub-árvore usando uma forma simples de memoização (eg. programação dinâmica).