El problema Sum Root to Leaf Numbers pide recorrer una árbol, formar un número por cada camino desde la raíz hasta una hoja y sumar todos esos números. Aquí verás cómo plantear la solución usando DFS y conversión a string para construir cada valor.

¿Qué pide el problema Sum Root to Leaf Numbers?

Cada nodo guarda un dígito entero. Al recorrer un camino completo desde la raíz hasta una hoja, los dígitos forman un número. La tarea consiste en sumar todos esos números y devolver el resultado final.

Mira este ejemplo concreto del transcript [01:00]: una árbol con tres caminos genera los números 135, 138 y 171. La suma da 444. Ese es el valor que la función debe retornar.

¿Qué devuelve Sum Root to Leaf Numbers? Devuelve un entero que representa la suma de todos los números formados por los caminos desde la raíz hasta cada hoja del árbol.

No importa si la árbol es binaria o enaria. Lo único que cambia es si revisas hijo izquierdo y derecho, o si iteras sobre todos los hijos. La lógica de fondo es la misma.

¿Por qué usar DFS para recorrer el árbol?

Cuando necesitas construir un camino completo hasta el final antes de procesarlo, DFS (Depth First Search) es la opción natural. Te permite bajar nodo por nodo, llegar a una hoja, registrar el resultado y luego retroceder para explorar otra rama.

Esto lo viste explicado en la clase [02:15]: parte del modelo base de DFS implementado en una clase anterior y, sobre esa estructura, resuelve los subproblemas específicos de este ejercicio.

¿Cómo convertir los nodos del camino en un número?

Aquí aparece el truco más interesante. Si intentas calcular 135 multiplicando por potencias de 10, te enfrentas a un problema: no sabes cuántos dígitos tendrá el número final mientras vas bajando por la árbol.

La solución que se propone [03:30] es construir el número como string:

• Empiezas con el dígito de la raíz, por ejemplo 1.
• Al llegar al siguiente nodo, concatenas su valor convertido a string, por ejemplo 3, y obtienes "13".
• Sigues bajando y concatenas 5 para tener "135".
• Al llegar a la hoja, conviertes "135" a entero con un cast.

Este enfoque mantiene complejidad O(1) en cada paso de concatenación lógica y evita el cálculo aritmético con potencias desconocidas.

¿Por qué concatenar como string en vez de multiplicar por 10? Porque al recorrer desde la raíz no sabes la posición final de cada dígito. Concatenar evita calcular potencias de 10 con un exponente que aún no conoces.

¿Cómo guardar la suma total durante la recursión?

Tienes dos caminos para acumular el resultado. Cada uno tiene un costo distinto en memoria.

• Guardar cada número en una lista y sumar al final. Esto implica complejidad O(N) en espacio.
• Mantener una variable entera que actúe como acumulador global. Cada vez que llegas al caso base, sumas el número del camino actual a esa variable.

La segunda opción es más eficiente en espacio. El caso base se activa cuando el nodo actual ya no tiene hijos: ahí conviertes el string del camino a entero y lo sumas al acumulador [05:10].

Cuando la recursión termina de explorar todas las ramas, retornas ese acumulador y tienes la respuesta.

¿Cuál es la complejidad de esta solución?

En tiempo, recorres cada nodo una sola vez. Por eso la complejidad se expresa como la cantidad de nodos del árbol. En notación de grafos, esto equivale a V + E, donde V es el número de vértices y E el número de aristas [06:20].

En espacio, depende de cómo manejes el acumulador. Con la variable entera, el costo adicional viene dado por la profundidad de la recursión, no por almacenar todos los caminos.

Reto: ¿cómo calcular el número sin usar strings?

El desafío que queda planteado es interesante: construye el número 135 usando solo operaciones aritméticas, sin convertir a string en ningún momento. Piensa en cómo combinar multiplicación y suma para ir desplazando los dígitos a medida que bajas por el árbol.

Deja tu propuesta en los comentarios y nos vemos en la siguiente clase para implementar la solución completa en código.