Playground: Sum Root to Leaf Numbers

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

Harold Zurita Simon

student•

Solución.. 😄 . . . .

def sum_numbers(raiz, valor_actual=0):
   if raiz is None:
      return 0
   
   nuevo_valor = valor_actual * 10 + raiz.valor

   if raiz.izquierda is None and raiz.derecha is None:
      return nuevo_valor
   
   suma_izquierda = sum_numbers(raiz.izquierda, nuevo_valor)
   suma_derecha = sum_numbers(raiz.derecha, nuevo_valor)

   return suma_izquierda + suma_derecha

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

Ivan Scaglioni

student•

Mi solución . . . .

def sum_numbers(raiz):
   respuesta = 0
   arrayNode = [raiz]
   arrayString = ['']
   index = 0

   for node in arrayNode:
      numero = arrayString.pop()

      if node.izquierda != None:
         arrayNode.insert(index +1, node.izquierda)
         arrayString.append(numero + str(node.valor))

      if node.derecha != None:
         arrayNode.insert(index + 2, node.derecha)
         arrayString.append(numero + str(node.valor))

      if node.izquierda == None and node.derecha == None:
         respuesta = respuesta +  int(numero + str(node.valor))

      index = index +1

   return respuesta

Platzi Team

student•

def sum_numbers(raiz):
    def dfs(nodo, acumulado):
        if nodo is None:
            return 0
        
        # Construimos el número concatenando (acumulado * 10 + valor actual)
        nuevo_valor = acumulado * 10 + nodo.valor
        
        # Si es una hoja, devolvemos este número
        if nodo.izquierda is None and nodo.derecha is None:
            return nuevo_valor
        
        # Si no es hoja, seguimos sumando ambos subárboles
        return dfs(nodo.izquierda, nuevo_valor) + dfs(nodo.derecha, nuevo_valor)

    return dfs(raiz, 0)


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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

John Eduard Meneses González

student•

My Solution

Hans Uriel Diaz Aguilar

student•

Les comparto la solución:

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

def sum_numbers(raiz):
   def dfs(nodo, acum_sum):
        if nodo is None:
            return 0
        acum_sum = acum_sum * 10 + nodo.valor

        if (nodo.izquierda is None and nodo.derecha is None):
            return acum_sum 
        return dfs(nodo.izquierda, acum_sum) + dfs(nodo.derecha, acum_sum)
   
   return dfs(raiz, 0)

Andres Silva Vega

student•

Alexis Exequiel Miranda

student•

Sin spoilers...

def sum_numbers(raiz, valor_acumulado: int = 0):
   # Caso base: si el nodo actual es nulo, no hay nada que sumar
   if raiz is None:
      return 0
   
   # Calcula el nuevo valor acumulado multiplicando el valor acumulado actual por 10 y sumando el valor del nodo actual
   nuevo_valor_acumulado = valor_acumulado * 10 + raiz.valor

   # Si el nodo actual es una hoja (no tiene hijos), retorna el valor acumulado actual
   if raiz.izquierda is None and raiz.derecha is None:
      return nuevo_valor_acumulado

   # Si el nodo actual no es una hoja, suma los resultados de las llamadas recursivas a los hijos izquierdo y derecho
   return sum_numbers(raiz.izquierda, nuevo_valor_acumulado) + sum_numbers(raiz.derecha, nuevo_valor_acumulado)

Carlos Hernandez

student•

Mi solución:

def sum_numbers(raiz, valor_anterior = '', suma = 0):
   nueva_suma = valor_anterior + str(raiz.valor)

   if (not raiz.izquierda and not raiz.derecha):
      return int(nueva_suma)
   else:
      suma += sum_numbers(raiz.izquierda, nueva_suma, suma) + sum_numbers(raiz.derecha, nueva_suma, suma)
      return suma
   
class Nodo:
   def __init__(self, x):
      self.valor = x
      self.izquierda = None
      self.derecha = None
```def sum\_numbers(raiz, valor\_anterior = '', suma = 0):   nueva\_suma = valor\_anterior + str(raiz.valor)
   if (not raiz.izquierda and not raiz.derecha):      return int(nueva\_suma)   else:      suma += sum\_numbers(raiz.izquierda, nueva\_suma, suma) + sum\_numbers(raiz.derecha, nueva\_suma, suma)      return suma   class Nodo:   def \_\_init\_\_(self, x):      self.valor = x      self.izquierda = None      self.derecha = None

Carlos Hernandez

student•

def sum_numbers(raiz, valor_anterior = '', suma = 0):
   nueva_suma = valor_anterior + str(raiz.valor)

   if (not raiz.izquierda and not raiz.derecha):
      return int(nueva_suma)
   else:
      suma += sum_numbers(raiz.izquierda, nueva_suma, suma) + sum_numbers(raiz.derecha, nueva_suma, suma)
      return suma
   
class Nodo:
   def __init__(self, x):
      self.valor = x
      self.izquierda = None
      self.derecha = None

Bryan Castano

student•

#Sum all Node.Values in a Tree from root to leaves ...
def sum_numbers(raiz, currentValue = 0 ) -> int:
   # Tu código aquí 👇.....

   if  raiz is None :

      return 0 
   
   newValue = currentValue * 10 + raiz.valor 

   if ( raiz.izquierda is None and raiz.derecha is None ) :

      return newValue

   LeftSum = sum_numbers( raiz.izquierda , newValue ) 

   rightSum = sum_numbers( raiz.derecha , newValue ) 

   treeSum = LeftSum + rightSum 

   return treeSum

Miguel Angel Reyes Moreno

student•

Les paso mi solución con código base de leetcode:

# Definition for a binary tree node.from typing import Optional

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

class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: def dfs(node, current_number): if not node: return 0 current_number = current_number * 10 + node.val if not node.left and not node.right: return current_number return dfs(node.left, current_number) + dfs(node.right, current_number) return dfs(root, 0)

root1 = TreeNode(1, 2, 3)root1.left = TreeNode(2)root1.right = TreeNode(3)solution = Solution()result = solution.sumNumbers(root1)print(f'result: {result}')

Yojan Antonio Pardo Zabala

student•

mi solucion con unos cuantos prints para ver que pasaba en cada iteración

def sum_numbers(raiz, valorAnterior = 0):
   # Tu código aquí 👇
   print(valorAnterior, raiz.valor)
   
   if raiz.izquierda == None and raiz.derecha == None:
      print(f'valor retorno caso base: [{valorAnterior + raiz.valor}]')
      return valorAnterior + raiz.valor

   valorAnterior = (valorAnterior+raiz.valor) * 10

   suma = sum_numbers(raiz.izquierda, valorAnterior) + sum_numbers(raiz.derecha, valorAnterior)
   print(f'valor retorno suma [{suma}]')
   return suma

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

Nicolas Guillen

student•

class Node { constructor(x) { this.value = x; this.left = null; this.right = null; }}

Juan Pablo Sanchez

student•

Si a alguien le interesa visualizar el arbolito 👌 ⭐ 1 /
2 3 / \ /
4 5 6 7

Jean Paul Barrit

student•

Otra solución por acá. No es la más eficiente, pero es fácil de entender

global lista
lista = []

def sum_numbers(raiz):
   global lista
   if (raiz == None):
      if (lista!=[]):
         lista.pop()
      return 0
   if (raiz.izquierda == None and raiz.derecha == None):
      lista += [raiz.valor]
      lista = list(reversed(lista))
      num = 0
      for i in range(0,len(lista)):
         num += lista[i] * 10 ** i
      lista = list(reversed(lista))
      return num + sum_numbers(raiz.izquierda) + sum_numbers(raiz.derecha)
   else:
      lista += [raiz.valor]
      leftSide = sum_numbers(raiz.izquierda)
      lista += [raiz.valor]
      righSide = sum_numbers(raiz.derecha)
      if (lista!=[]):
         lista.pop()
      return leftSide + righSide

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

Cristian Camilo Vargas Peña

student•

casi que no.. pero que satisfaccion :) .

def sum_numbers(raiz, valor_actual=0):
   if raiz is None:
      return 0
   
   nuevo_valor = valor_actual * 10 + raiz.valor

   if raiz.izquierda is None and raiz.derecha is None:
      return nuevo_valor
   
   suma_izquierda = sum_numbers(raiz.izquierda, nuevo_valor)
   suma_derecha = sum_numbers(raiz.derecha, nuevo_valor)

   return suma_izquierda + suma_derecha

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

def sum_numbers(raiz):
   respuesta = 0
   arrayNode = [raiz]
   arrayString = ['']
   index = 0

   for node in arrayNode:
      numero = arrayString.pop()

      if node.izquierda != None:
         arrayNode.insert(index +1, node.izquierda)
         arrayString.append(numero + str(node.valor))

      if node.derecha != None:
         arrayNode.insert(index + 2, node.derecha)
         arrayString.append(numero + str(node.valor))

      if node.izquierda == None and node.derecha == None:
         respuesta = respuesta +  int(numero + str(node.valor))

      index = index +1

   return respuesta

def sum_numbers(raiz):
    def dfs(nodo, acumulado):
        if nodo is None:
            return 0
        
        # Construimos el número concatenando (acumulado * 10 + valor actual)
        nuevo_valor = acumulado * 10 + nodo.valor
        
        # Si es una hoja, devolvemos este número
        if nodo.izquierda is None and nodo.derecha is None:
            return nuevo_valor
        
        # Si no es hoja, seguimos sumando ambos subárboles
        return dfs(nodo.izquierda, nuevo_valor) + dfs(nodo.derecha, nuevo_valor)

    return dfs(raiz, 0)


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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

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

def sum_numbers(raiz):
   def dfs(nodo, acum_sum):
        if nodo is None:
            return 0
        acum_sum = acum_sum * 10 + nodo.valor

        if (nodo.izquierda is None and nodo.derecha is None):
            return acum_sum 
        return dfs(nodo.izquierda, acum_sum) + dfs(nodo.derecha, acum_sum)
   
   return dfs(raiz, 0)

def sum_numbers(raiz, valor_acumulado: int = 0):
   # Caso base: si el nodo actual es nulo, no hay nada que sumar
   if raiz is None:
      return 0
   
   # Calcula el nuevo valor acumulado multiplicando el valor acumulado actual por 10 y sumando el valor del nodo actual
   nuevo_valor_acumulado = valor_acumulado * 10 + raiz.valor

   # Si el nodo actual es una hoja (no tiene hijos), retorna el valor acumulado actual
   if raiz.izquierda is None and raiz.derecha is None:
      return nuevo_valor_acumulado

   # Si el nodo actual no es una hoja, suma los resultados de las llamadas recursivas a los hijos izquierdo y derecho
   return sum_numbers(raiz.izquierda, nuevo_valor_acumulado) + sum_numbers(raiz.derecha, nuevo_valor_acumulado)

def sum_numbers(raiz, valor_anterior = '', suma = 0):
   nueva_suma = valor_anterior + str(raiz.valor)

   if (not raiz.izquierda and not raiz.derecha):
      return int(nueva_suma)
   else:
      suma += sum_numbers(raiz.izquierda, nueva_suma, suma) + sum_numbers(raiz.derecha, nueva_suma, suma)
      return suma
   
class Nodo:
   def __init__(self, x):
      self.valor = x
      self.izquierda = None
      self.derecha = None
```def sum\_numbers(raiz, valor\_anterior = '', suma = 0):   nueva\_suma = valor\_anterior + str(raiz.valor)
   if (not raiz.izquierda and not raiz.derecha):      return int(nueva\_suma)   else:      suma += sum\_numbers(raiz.izquierda, nueva\_suma, suma) + sum\_numbers(raiz.derecha, nueva\_suma, suma)      return suma   class Nodo:   def \_\_init\_\_(self, x):      self.valor = x      self.izquierda = None      self.derecha = None

def sum_numbers(raiz, valor_anterior = '', suma = 0):
   nueva_suma = valor_anterior + str(raiz.valor)

   if (not raiz.izquierda and not raiz.derecha):
      return int(nueva_suma)
   else:
      suma += sum_numbers(raiz.izquierda, nueva_suma, suma) + sum_numbers(raiz.derecha, nueva_suma, suma)
      return suma
   
class Nodo:
   def __init__(self, x):
      self.valor = x
      self.izquierda = None
      self.derecha = None

#Sum all Node.Values in a Tree from root to leaves ...
def sum_numbers(raiz, currentValue = 0 ) -> int:
   # Tu código aquí 👇.....

   if  raiz is None :

      return 0 
   
   newValue = currentValue * 10 + raiz.valor 

   if ( raiz.izquierda is None and raiz.derecha is None ) :

      return newValue

   LeftSum = sum_numbers( raiz.izquierda , newValue ) 

   rightSum = sum_numbers( raiz.derecha , newValue ) 

   treeSum = LeftSum + rightSum 

   return treeSum

def sum_numbers(raiz, valorAnterior = 0):
   # Tu código aquí 👇
   print(valorAnterior, raiz.valor)
   
   if raiz.izquierda == None and raiz.derecha == None:
      print(f'valor retorno caso base: [{valorAnterior + raiz.valor}]')
      return valorAnterior + raiz.valor

   valorAnterior = (valorAnterior+raiz.valor) * 10

   suma = sum_numbers(raiz.izquierda, valorAnterior) + sum_numbers(raiz.derecha, valorAnterior)
   print(f'valor retorno suma [{suma}]')
   return suma

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

global lista
lista = []

def sum_numbers(raiz):
   global lista
   if (raiz == None):
      if (lista!=[]):
         lista.pop()
      return 0
   if (raiz.izquierda == None and raiz.derecha == None):
      lista += [raiz.valor]
      lista = list(reversed(lista))
      num = 0
      for i in range(0,len(lista)):
         num += lista[i] * 10 ** i
      lista = list(reversed(lista))
      return num + sum_numbers(raiz.izquierda) + sum_numbers(raiz.derecha)
   else:
      lista += [raiz.valor]
      leftSide = sum_numbers(raiz.izquierda)
      lista += [raiz.valor]
      righSide = sum_numbers(raiz.derecha)
      if (lista!=[]):
         lista.pop()
      return leftSide + righSide

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

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo5 = Nodo(5)
nodo6 = Nodo(6)
nodo7 = Nodo(7)
nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6
nodo3.derecha = nodo7

response = sum_numbers(nodo1)
print(response)

Playground: Sum Root to Leaf Numbers

Introducción

Grafos y Árboles: Estructuras de Datos Avanzadas

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Aplicaciones Prácticas de Grafos en Tecnología e Industria

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Búsqueda en Profundidad (DFS) en Árboles y Grafos

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

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

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Resolución del Problema de Número de Islas con DFS

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

Implementación de "Número de Islas" con Recursión en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Propagación de Plagas en Matrices usando BFS en Java

Construcción de Puentes Cortos entre Islas en Matrices Binarias

Resolución del Problema Shortest Bridge con DFS y BFS

Playground: Shortest Bridge Between Islands

Búsqueda del camino más corto entre islas usando BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Algoritmo Backtracking: Solución de Problemas Complejos

Combinaciones de Letras en Números Telefónicos

Combinaciones de Letras a partir de un Número de Teléfono

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Generación de IPs válidas con backtracking en C++

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Búsqueda de Palabras en Matrices usando Backtracking y DFS

Playgrund: Word Search

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

Algoritmos y Estructuras de Datos en la Ingeniería