Sumar números de raíz a hoja en un árbol binario

Muy buenas, les saluda Luis y aquí les traigo otro tutorial.

Un problema de dificultad media de Leetcode

Sumar números de raíz a hoja es un problema interesante de Leetcode. El problema es de dificultad media y se trata de árboles binarios. Esta publicación es una solución explicada al problema.

Supongo que está familiarizado con Python y el concepto de árboles binarios. Si no es así, puede leer Este artículo Para empezar.

El problema

Dado un árbol binario cuyos nodos contienen valores 0-9, tenemos que encontrar la suma de todos los números formados por caminos de raíz a hoja.

Una hoja es un nodo que no tiene nodos secundarios. En un árbol binario, una ruta de raíz a hoja siempre es única. A continuación, se muestra el comportamiento esperado de la solución requerida:

En el árbol de la izquierda, la salida es 25. 25 es la suma de 12 y 13, que son los dos números que se forman a partir de 1 y visitando cada hoja. En el árbol de la derecha, la salida es 1026 ya que es la suma de los tres números 495, 491 y 40.

Las observaciones y las percepciones

La solución

Podemos hacer un pre-order recorrido del árbol en el que construimos un número de forma incremental y aprovechamos el hecho de que los números formados por nodos en el mismo subárbol tienen dígitos comunes.

Cuando terminemos de formar números en un subárbol, podemos retroceder e ir a otro subárbol.

Vamos a crear un Solution clase para abarcar nuestra solución.

Solution:

def sum_numbers(self, root: TreeNode) -> int:

La firma del método que se nos dio en el problema tiene un argumento: root, que es del tipo TreeNode . Una clase TreeNode es la siguiente (de Leetcode):

TreeNode:

     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

De la observación n. ° 2, observe que se puede agregar el dígito de un nodo a sus antepasados ​​moviendo todos los dígitos del número formado por los antepasados ​​a la derecha en 1 lugar y agregando el dígito del nodo actual.

Los dígitos se pueden mover multiplicando el número formado por los antepasados ​​por 10 (ya que estamos en base 10). Por ejemplo:

495 = 49 x 10 + 5

Por lo tanto, podemos realizar un seguimiento de los dígitos actuales en un número entero. Esto es importante porque no incurriremos en espacio de almacenamiento adicional para tamaños de entrada más altos.

Podemos pasar este valor en el propio parámetro de la función. Dado que la firma del método dada solo puede tener un parámetro, creemos un método sum_root_to_leaf_helper.

Podemos pensar en el sum_root_to_leaf_helper método de forma recursiva y procesar cada nodo de manera diferente en función de si es una hoja o no.

Si el nodo actual es un None, podemos simplemente devolver 0 porque no cuenta.

Así, nuestro sum_root_to_leaf_helper. El método será el siguiente:

sum_root_to_leaf_helper(node, partial_sum=0):
            if not node:
                return 0
            partial_sum = partial_sum * 10 + node.val
            # Leaf
            if not node.left and not node.right:
                return partial_sum
            # Non Leaf 
            return (sum_root_to_leaf_helper(node.left, partial_sum) + sum_root_to_leaf_helper(node.right, partial_sum))

Usamos un valor predeterminado para que la suma parcial sea 0.

En nuestro método principal, queremos incluir el sum_root_to_leaf_helper como método anidado y simplemente pase el parámetro de nodo. Finalmente, así es como se ve nuestra solución:

Solution:

    def sumNumbers(self, root: TreeNode) -> int:
        def sum_root_to_leaf_helper(node, partial_sum=0):
            if not node:
                return 0
            partial_sum = partial_sum * 10 + node.val
            # Leaf
            if not node.left and not node.right:
                return partial_sum
            # Non Leaf 
            return (sum_root_to_leaf_helper(node.left, partial_sum) + sum_root_to_leaf_helper(node.right, partial_sum))
    
        return sum_root_to_leaf_helper(root)

La complejidad algorítmica

Cuando se nos ocurre una solución, es importante analizar su complejidad algorítmica no solo para estimar su desempeño, sino también para identificar áreas de mejora y reflexionar sobre nuestras habilidades de resolución de problemas.

Siempre debemos hacernos la pregunta: ¿podemos hacerlo mejor que X? Donde X es la complejidad actual de nuestra solución.

Hora:

Nuestra solución es una modificación del recorrido de preorden de búsqueda en profundidad donde visitamos todos los nodos exactamente una vez y realizamos un cálculo trivial (mover dígitos por multiplicación de enteros).

Por lo tanto, nuestro tiempo de ejecución es simplemente O(N) dónde N representa el número de nodos en el árbol dado. Una solución mejor que O(N) no parece posible porque para construir un número a partir de dígitos, necesitamos conocer todos los dígitos (y así visitar todos los nodos).

Espacio:

En términos de almacenamiento, incurrimos en un alto costo en la pila de llamadas de recursividad que se acumula a medida que nuestro sum_root_to_leaf_helper se llama a sí mismo. Estas llamadas se acumulan mientras uno espera que termine otro.

Puedes leer este artículo para saber más sobre las pilas de llamadas recursivas.

Es posible hacerlo mejor que O(N) mediante el uso de un recorrido de preorden de Morris. La idea básica es vincular un nodo y su predecesor temporalmente. Puedes leer más sobre esto aquí.

Gracias por leer este tutorial.