Playground: Sum Root to Leaf Numbers

Curso de Algoritmos Avanzados: Grafos y Árboles

Introducción

¿Qué es un grafo?

¿Qué es un árbol?

¿Qué es recursión?

Aplicaciones reales de grafos y árboles

Formas de representar un grafo

DFS

Análisis de DFS: algoritmo de búsqueda en profundidad

Programando DFS de forma recursiva

Otras formas de programar DFS

Recorridos y profundidad de un Árbol

Sum Root to Leaf Numbers: análisis del problema

Solución de Sum Root to Leaf Numbers

Playground: Sum Root to Leaf Numbers

Programando Sum Root to Leaf Numbers en Golang

Number of Islands: análisis del problema

Solución de Number of Islands

Playground: Number of Islands

Programando Number of Islands en Python

Ejercicios recomendados de DFS

Ejercicios resueltos de DFS

BFS

Análisis de BFS: algoritmo de búsqueda en anchura

Programando BFS con Python

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

Solución de Minimum Knights Moves

Playground: Minimum Knights Moves

Programando Minimum Knights Moves con Python

Rotting Oranges: análisis del problema

Solución de Rotting Oranges

Playground: Rotting Oranges

Rotting Oranges con Java

Shortest Bridge Between Islands: análisis del problema

Solución de Shortest Bridge Between Islands

Playground: Shortest Bridge Between Islands

Programando Shortest Bridge Between Islands con Python

Ejercicios recomendados de BFS

Ejercicios resueltos de BFS

Backtrack

Algoritmo de Backtrack

Letter Combinations of a Phone Number: análisis del problema

Solución de Letter Combinations of a Phone Number

Programando Letter Combinations of a Phone Number con C++

Playground: Letter Combinations of a Phone Number

Restore IP Addresses: análisis del problema

Programando Restore IP Addresses con C++

Playground: Restore IP Addresses

Word Search: análisis del problema

Solución de Word Search

Playgrund: Word Search

Programando Word Search JavaScript

Reto: N Queens Puzzle

Ejercicios recomendados de Backtrack

Ejercicios resueltos de Backtrack

Próximos pasos

¿Qué otros algoritmos y tipos de grafos puedes aprender?

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Si ya tienes una cuenta,

Aportes 7

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Harold Zurita Simon

hace un año

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)

Miguel Ángel Reyes Moreno

hace un mes

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

hace 8 meses

mi solucion con unos cuantos prints para ver que pasaba en cada iteración ```python 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

hace 9 meses

JS class Node { constructor(x) { this.value = x; this.left = null; this.right = null; }} function sumNumbers(root) { let sum = 0; if (root == null) { return 0; } function dfs(node, previous = "") { // if it's a leaf then add their digits to the sum if (node.left == null && node.right == null) { sum += Number(previous + node.value); } // if it's not a leaf then keep going down the tree if (node.left != null) { dfs(node.left, previous + node.value); } if (node.right != null) { dfs(node.right, previous + node.value); } } dfs(root); return sum;}

Juan Pablo Sanchez

hace un año

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

Ivan Scaglioni

hace un año

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

Jean Paul Barrit

hace un año

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)