Suma de Números de Raíz a Hoja en Árboles

Clase 11 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Cómo resolver el problema "Some Root to Leaf Numbers"?

El problema "Some Root to Leaf Numbers" consiste en recorrer un árbol para encontrar todos los caminos desde la raíz hasta las hojas. Cada nodo del árbol tiene un número entero y debemos construir números a partir de estos caminos, sumar todos esos números al final y retornar el valor total. Te detallo el proceso y las soluciones propuestas.

¿Qué es un árbol en este contexto?

En este contexto, un árbol es una estructura de datos jerárquica que consiste en nodos. Cada nodo almacena un valor entero y puede tener uno o varios nodos hijos. Dependiendo de su estructura, un árbol puede ser binario (cada nodo tiene como máximo dos hijos) o n-ario (con varios hijos). La manera de recorrer el árbol variará dependiendo de su tipo, pero el problema central sigue siendo el mismo: encontrar todos los caminos desde la raíz hasta las hojas.

¿Cómo encontrar los caminos en un árbol?

Para abordar este problema, podemos emplear la técnica de búsqueda en profundidad (DFS, por sus siglas en inglés). DFS es ideal para este tipo de problemas porque nos permite explorar un camino completo antes de retroceder y probar con uno nuevo. Durante este proceso, vamos creando números a partir de los valores en cada nodo.

Implementación de DFS

Durante la implementación de DFS, deberemos realizar las siguientes acciones:

Recorrer el árbol: Implementa un recorrido mediante DFS que nos permita visitar cada nodo del árbol.
Construir los números: A medida que recorre cada camino, concatena los valores de los nodos para crear un número que representa ese camino desde la raíz hasta una hoja.
Sumar los números: Una vez alcanzada una hoja, convierte la secuencia creada en un número entero y agrégalo a un total acumulado.

Ejemplo de recorrido

Imagina un árbol con caminos que generan los números 135, 138 y 171. La suma de estos números es 444, que es el valor final que se devolvería.

¿Cómo construimos los números a partir de un camino?

La construcción del número a partir de un camino puede parecer complicada. Veamos cómo hacerlo con claridad utilizando un enfoque basado en cadenas de caracteres en lugar de complicados cálculos aritméticos.

Convertir números a cadenas

Inicializar y recorrer: Comienza con el primer nodo del camino. Asegúrate de almacenar y concatenar cada valor en una forma de cadena.
Concatenación de cadenas: Durante el recorrido, convierte cada número entero a una cadena y concatena al resultado actual.
Conversión a entero: Al llegar al final del camino, es decir, una hoja, convierte la cadena completa en un número entero.

Este método simplifica considerablemente la operación, evitando complicaciones matemáticas innecesarias.

¿Cómo gestionamos la suma de los números finales?

Al implementar el algoritmo es importante gestionar adecuadamente el almacenamiento de sumas:

Almacenamiento acumulativo: En lugar de crear una lista con todos los números generados, almacenamos de manera directa la suma acumulada. Es decir, cada vez que finalizamos un camino (llegamos a una hoja), convertimos el camino actual en un número y lo sumamos al total acumulado.

Este enfoque mejora la eficiencia espacial, ya que evita el almacenamiento de grandes cantidades de datos intermedios.

¿Cuál es la complejidad del algoritmo?

El algoritmo propuesto sigue un enfoque DFS, lo que significa que cada nodo del árbol se visita exactamente una vez. Por lo tanto, la complejidad temporal es O(N), donde N es el número de nodos en el árbol. Además, como solo almacenamos una suma acumulada, la complejidad espacial se mantiene en un nivel óptimo.

¿Puedes aceptar el reto?

Finalmente, se plantea un reto: ¿puedes pensar en una manera de calcular estos números sin usar cadenas? ¿Cómo podrías combinar operaciones matemáticas como la suma y multiplicación para construir estos números? Reflexiona sobre ello y comparte tus ideas en los comentarios. ¡Continúa aprendiendo y motivándote para enfrentar nuevos desafíos!

Pro Code

student•

El cálculo de los números sin utilizar un string lo realizaría de la siguiente manera:

El número que guardé lo multiplicaría por 10 y luego sumaría el valor actual. Ej.:

valor guardado = 1, nuevo valor = 3 -> 1 * 10 = 10, 10 + 3 = 13

valor guardado = 13, nuevo valor = 5 -> 13 * 10 = 130, 130 + 5 = 135

Mario Alberto Hernández Pintor

student•

Si los valores de los nodos son de más de un digito se tendria que agregar algo como:

var factor = hijo.valor.toString().length;
const nueva_suma = suma_acumulada*(10**factor) + hijo.valor;

Es decir, agregar tantos ceros a la derecha a la suma acumulada como de dígitos tenga el siguiente valor.

Mario Alberto Hernández Pintor

student••

function sumarCaminosRaizAHoja(raiz) {
    // derecha a izquierda
    
    // Almacenamos [nodo, suma_acumulada]
    const pila = [ [raiz, raiz.valor] ]; 
    const sumas_caminos = [];

    while (pila.length > 0) {
        // Sacamos el estado de la cima (DFS)
        const [nodo_actual, suma_acumulada] = pila.pop(); 

        // 1. CONDICIÓN DE HOJA
        if (nodo_actual.hijos.length === 0) {
            // Encontramos una hoja, el camino está completo
            sumas_caminos.push(suma_acumulada);
            continue; // Pasamos a la siguiente iteración 
        }

        // 2. EXPANSIÓN DE HIJOS
        for (const hijo of nodo_actual.hijos) {
            // Calculamos el nuevo estado para el hijo
            var factor = hijo.valor.toString().length;
            const nueva_suma = suma_acumulada*(10**factor) + hijo.valor;
            
            // Insertamos el nuevo estado en la pila
            pila.push([hijo, nueva_suma]);
        }
    }

    return sumas_caminos;
}

Hans Uriel Diaz Aguilar

student•

Les comparto mi solución:

def sum_root_numbers(tree, root):
    def dfs(node, acum_sum):
        acum_sum = acum_sum * 10 + node
        if not tree[node]:
            return acum_sum
        
        total = 0
        for child in tree[node]:
            total += dfs(child, acum_sum)
        return total

    return dfs(root, 0)

tree2 = {
    1: [3, 5, 7],
    3: [8, 9],
    4: [],
    5: [],
    7: [4],
    8: [],
    9: []
}

print(sum_root_numbers(tree2, 0))

Kellbis Salazar

student•

Gabriel Cavedal

student•

from functools import reduce

def dfs(n, branch = [], r = []):
    if n is None:
        return

    left = n['left']
    right = n['right']

    branch.append(n['data'])

    if not left and not right:
        print(branch)
        # reduce va recorriendo de izquierda a derecha a branch, iterando, y el lambda usa acc(umulado) para ir guardando el valor que se multiplica por 10 (moviendo el número a la derecha) y sumándole el nuevo número al final.
        r.append(reduce(lambda acc, num: acc * 10 + num, branch))
        branch.pop()
        
    if left is not None:
        dfs(left, branch)

    if right is not None:
        dfs(right, branch)
    
    return r

binary_tree = {
    'data': 1,
    'left': {
        'data': 2,
        'left': {
            'data': 4,
            'left': None,
            'right': None
        },
        'right': {
            'data': 5,
            'left': {
                'data': 8,
                'left': {
                    'data': 9,
                    'left': None,
                    'right': None
                },
                'right': None,
            },
            'right': None
        }
    },
    'right': {
        'data': 3,
        'left': {
            'data': 6,
            'left': None,
            'right': None
        },
        'right': {
            'data': 7,
            'left': None,
            'right': None
        }
    }
 }

if __name__ == "__main__":
    r = dfs( n = binary_tree)
    print(r)
    # acá sólo sumamos todos los números
    print(reduce(lambda acc, num: acc + num, r))

Santiago García Rincón

student•

<
# Función para realizar DFS en un grafo dado
lista = []
def dfs(graph, node, visited, num):
    
    num += str(node)
    visited[node] = True
    # Recorrer todos los nodos adyacentes al nodo actual
    for neighbor in graph[node]:
        if not visited[neighbor]:
            # Si el vecino no ha sido visitado, realizar DFS en él
            dfs(graph, neighbor, visited, num)
        
    if  len(graph[node]) == 1:
        lista.append(int(num))
    return False

# Ejemplo de uso
if __name__ == "__main__":
    # Grafo representado como listas de adyacencia
    graph = {
        0: [1, 2],
        1: [0, 3, 4],
        2: [0, 5],
        3: [1],
        4: [1,6],
        5: [2],
        6:[4,7],
        7:[6,8],
        8:[7]

    }

    # Inicializar un arreglo para llevar un seguimiento de los nodos visitados
    visited = [False] * len(graph)

    # Realizar DFS desde el nodo 0
    dfs(graph, 0, visited,"")
    print(sum(lista))

>

Angélica María Celis Torres

student•

Los arboles son un tipo de grafo, pero usualmente no se habla de ellos como grafos. Una buena manera de representarlos es usando arrays, por ejemplo el arbol que la profe usa puede representarse como: [ 1 3 7 5 8 1], el orden de los numeros en el array varia de acuerdo a como se recorra el arbol. Si observas, usando un array en lugar de una matrix puedes ahorrar mucho espacio, ya que sabes que en un arbol no hay un par de nodos que tengan aristas apuntando en las dos direcciones ( A <--> B ), y que no existen ciclos.

Daniel Ortiz

student•

Me imagine como seria la estructura en python

tree = [
    {
        "v": 1,
        "child": [
            {
                "v": 2,
                "child": []
            },
            {
                "v": 3,
                "child": [
                    {
                        "v": 4,
                        "child": []
                    }
                ]
            }
        ]
    },

]
def sum_tree(tree, sum_tree_val:str):
    sum_tree_val= sum_tree_val + str(tree['v'])
    if tree['child'] is not None:
        for child in tree['child']:
            return sum_tree(child, str(sum_tree_val))
    return sum_tree_val
total = 0
for root in tree:

    if root.get('child') is not None:
       for child in root['child']:

           total=total+int(sum_tree(child,sum_tree_val=str(root.get('v'))))
print(total)

EDSEL Laucho Di Meo

student•

Mi solución al problema numericamente

def sum_root_to_leaf(root, max_height):

    total_numbers = []

    if root.children[0]:
        if check_max_depth(root.children[0]) == 1:
            total_numbers.append(root.value * (10**(check_max_depth(root.children[0]))) + root.children[0].value)
        else:
            for child_number in sum_root_to_leaf(root.children[0], max_height):
                total_numbers.append(root.value * (10**(check_max_depth(root.children[0]))) + child_number)
    
    if len(root.children) == 2:
        if root.children[1]:
            if check_max_depth(root.children[1]) == 1:
                total_numbers.append(root.value * (10**(check_max_depth(root.children[1]))) + root.children[1].value)
            else:
                for child_number in sum_root_to_leaf(root.children[1], max_height):
                    total_numbers.append(root.value * (10**(check_max_depth(root.children[1]))) + child_number)

    if max_height == check_max_depth(root):
        return sum(total_numbers)

    return total_numbers

Harold Zurita Simon

student•

Hola 😄, les comparto mi solución en js, siento que no es la mejor solución pero lo logré 😅.. . excerciseSRLN.js:

var soluciones = [];

// Función
const solSRLN = function (raiz, num) {
  if (!raiz) {
    return "";
  }

  num += raiz.valor;
  solSRLN(raiz.izquierda, num);
  solSRLN(raiz.derecha, num);

  if (!raiz.izquierda && !raiz.derecha) {
    soluciones.push(num);
  }
};

// Árbol
export const arbolSRLN = {
  valor: 1,
  izquierda: {
    valor: 3,
    izquierda: {
      valor: 5,
      izquierda: null,
      derecha: null,
    },
    derecha: {
      valor: 8,
      izquierda: null,
      derecha: null,
    },
  },
  derecha: {
    valor: 7,
    izquierda: null,
    derecha: {
      valor: 1,
      izquierda: null,
      derecha: null,
    },
  },
};

// Prueba
solSRLN(arbolSRLN, "");
var res = soluciones.reduce((acc, item) => Number(item) + acc, 0);
console.log("La solución es: " + res);

. Output:

José Ramón García

student•

Comparto mi solución

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

class Grafo:
    def __init__(self, primer_nodo):
        self.cabeza = primer_nodo

def sum_root(raiz, base = 0):
    if not raiz or not raiz.valor: return 0
    base = base*10 + raiz.valor
    base_izq = sum_root(raiz.izquierda, base=base)
    base_der = sum_root(raiz.derecha, base = base)
    if raiz.izquierda or raiz.derecha:
        return base_izq + base_der
    return base

def agregar_valores(nodo, izq=None, der= None):
    izq = Nodo(izq)
    der = Nodo(der)
    nodo.izquierda = izq
    nodo.derecha = der
    return nodo

raiz = Nodo(1)
A = agregar_valores(nodo= raiz, izq = 2, der = 8)
B = agregar_valores(nodo=raiz.izquierda, izq=3, der=5)
C = agregar_valores(nodo=raiz.derecha, izq= 9)
E = agregar_valores(nodo=B.derecha, izq = 6, der=7)