Desafío: Dado un árbol binario * no vacío*, encuentre la suma máxima de ruta. Para este problema, una ruta de acceso se define como cualquier secuencia de nodos desde un nodo inicial a cualquier nodo en el árbol a lo largo de las conexiones padre-hijo. La ruta debe contener al menos un nodo y no necesita pasar por la raíz:

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

Ejemplo #2:

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

El Desafío

Como su nombre indica, un árbol binario es un tipo popular de estructura de datos basada en árboles. Para apoyar su eficiencia en el tiempo y el espacio, los árboles a menudo están representados por una clave y dos o más nodos de hojas, similares a las siguientes estructuras:

As one may guess, recursion is also a common property of tree-based structures. Aunque la mayoría de las funciones recursivas son mal vistas en aplicaciones reales, los árboles permiten determinadas eficiencia de cada nodo hoja también puede representar a otro árbol:

Si no se entiende correctamente, los árboles pueden generar confusión y complejidad adicional. Para resolver nuestro desafío de código, necesitaremos idear un método consistente para navegar por nuestro árbol y una forma de comparar todas las permutaciones posibles.

Trabajemos visualizando nuestras ideas antes de enviarlas al código. Para empezar, primero abordaremos cómo navegar por el árbol. Dado que las estructuras basadas en árboles incorporan una propiedad conceptual adicional de *profundidad*, normalmente no se aplican técnicas simples como la enumeración rápida. En su lugar, podemos usar algoritmos de recorrido específicos como la búsqueda de profundidad o amplitud primero (por ejemplo, DFS y BFS respectivamente). A pesar de que el tema de BFS es lo suficientemente detallado para una nueva discusión, podemos concluir que esta sería la forma normal en que uno atravesaría dicha estructura. Sin embargo, dado que estamos trabajando con un Árbol Binario, podemos aplicar eficiencias algorítmicas específicas para ayudar a acortar el proceso transversal.

Entonces, ¿qué es un Árbol Binario? Esencialmente, es una matriz estándar que se visualiza como un árbol. En este caso, se hace hincapié en los aspectos de visualización, ya que esto afectará la forma en que navegamos por la estructura. Por ejemplo, para cada nodo, sus nodos hijos de hoja izquierda y derecha se pueden calcular usando estas fórmulas simples:

Como se discutió, estas fórmulas funcionan porque la estructura subyacente de nuestro árbol es una Matriz. Esto difiere de otras estructuras como un árbol B, Trie o Gráfico donde se aplicaría una estructura de datos personalizada específica para representar un modelo.

Hacer comparaciones

Dado que nuestro Árbol binario en realidad no es más que una matriz, podemos usar enumeración básica para iterar a través de todos los valores. Sin embargo, aplicaremos nuestras fórmulas para determinar nuestros nodos de hojas hijos. Una vez establecido, podemos rastrear los totales de cada sub-árbol usando una forma simple de memoización (ej. programación dinámica).