Introducci贸n

1

驴Qu茅 es un grafo?

2

驴Qu茅 es un 谩rbol?

3

驴Qu茅 es recursi贸n?

4

Aplicaciones reales de grafos y 谩rboles

5

Formas de representar un grafo

DFS

6

An谩lisis de DFS: algoritmo de b煤squeda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un 脕rbol

10

Sum Root to Leaf Numbers: an谩lisis del problema

11

Soluci贸n de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: an谩lisis del problema

15

Soluci贸n de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

An谩lisis de BFS: algoritmo de b煤squeda en anchura

21

Programando BFS con Python

22

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

23

Soluci贸n de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: an谩lisis del problema

27

Soluci贸n de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: an谩lisis del problema

31

Soluci贸n de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

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

38

Soluci贸n de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: an谩lisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: an谩lisis del problema

45

Soluci贸n de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Pr贸ximos pasos

51

驴Qu茅 otros algoritmos y tipos de grafos puedes aprender?

52

驴Quieres m谩s cursos avanzados de algoritmos?

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Soluci贸n de Sum Root to Leaf Numbers

11/52
Recursos

Aportes 5

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

<
# 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))

> 

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

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)

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

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: