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

Programando Sum Root to Leaf Numbers en Golang

13/52
Recursos

Aportes 11

Preguntas 0

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad?

Solución en java

class Solution {
    static int total;
    public int sumNumbers(TreeNode root) {
        total = 0;
        dfs(root, 0);
        return total;
    }
    static void dfs(TreeNode root, int parent) {
        int value = (parent * 10) + root.val;
        if(root.left == null && root.right == null){
            total += value;
            return;
        }

        if(root.left != null) {
            dfs(root.left, value);
        }

        if(root.left != null) {
            dfs(root.right, value);
        }
        
        return;

    }
}

Solución en c++

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int value;
    vector<Node> childrens;
};

int dfs(const Node &root, int path, int &sum)
{
    if (root.childrens.size() == 0)
    {
        sum += path;
        return sum;
    }

    for (int i = 0; i < root.childrens.size(); i++)
    {
        dfs(root.childrens[i], path * 10 + root.childrens[i].value, sum);
    }
    return sum;
}

int main()
{
    // root
    Node root;
    root.value = 1;

    // child1
    Node child1;
    child1.value = 2;

    // grandchild1
    Node grandchild1;
    grandchild1.value = 4;
    // grandchild2
    Node grandchild2;
    grandchild2.value = 1;

    child1.childrens.push_back(grandchild1);
    child1.childrens.push_back(grandchild2);

    // child2
    Node child2;
    child2.value = 3;
    root.childrens.push_back(child2);

    root.childrens.push_back(child1);
    int result = 0;
    dfs(root, root.value, result);

    cout << result << endl;

    return 0;
}

No hay solucion que alguien hiciera en JS Javascript? :( jaja en cuanto pueda la hago y la subo jeje
Puede ser que el error en el codigo es que la variable caminoActual nunca se regenera?

Esta es mi solución en Kotlin:

data class Node(
    val value: Int,
    val children: List<Node>? = null,
)

fun main() {
    val root = Node(
        value = 1,
        children = listOf(
            Node(
                value = 3,
                children = listOf(
                    Node(value = 5),
                    Node(value = 8),
                )
            ),
            Node(
                value = 7,
                children = listOf(
                    Node(1)
                )
            )
        )
    )
    val total = dfs(root, "")
    println("The sum is: $total")
}

fun dfs(node: Node, number: String): Int {
    if (node.children == null) {
        return "$number${node.value}".toInt()
    }
    var total = 0
    node.children.forEach {
        total += dfs(it, "$number${node.value}")
    }

    return total
}

Esta es mi solucion en Node.js

var total = 0;

const sumNumbers = (root) => {
    if (nodeIsEmpty(root)) return 0;

    let sumTxt = String(root.content);
    dfs(root, sumTxt);

    console.log("Total ", total);
}

const dfs = (node, sumTxt) => {
    if (nodeIsEmpty(node.right) && nodeIsEmpty(node.left)) {
        total = total + Number(sumTxt);
    };

    calculateSum(node.right, sumTxt, total);
    calculateSum(node.left, sumTxt, total);
}

const nodeIsEmpty = (node) => {
    return node == undefined || Object.keys(node).length == 0;
}

const calculateSum = (node, sumTxt) => {
    if (nodeIsEmpty(node)) return;

    dfs(node, sumTxt + String(node.content));
}

const root = {
    content: 1,
    visited: false,
    right : {
        content: 3,
        visited: false,
        right : {
            content: 5,
            visited: false,
            right: {},
            left: {}
        },
        left: {
            content: 8,
            visited: false,
            right: {},
            left: {}
        }
    },
    left: {
        content: 7,
        visited: false,
        right: {},
        left: {
            content: 1,
            visited: false,
            right: {},
            left: {}
        }
    }
}

sumNumbers(root);
Aquí está mi solución, un poco rudimentaria pero sirve. ```js totalF = 0 class Node: def __init__(self, valor): self.valor = valor self.izquierda = None self.derecha = None nodo1 = Node(1) nodo2 = Node(2) nodo3 = Node(3) nodo4 = Node(4) nodo5 = Node(5) nodo6 = Node(6) nodo1.izquierda = nodo2 nodo1.derecha = nodo3 nodo2.izquierda = nodo4 nodo2.derecha = nodo5 nodo3.izquierda = nodo6 def sum_numbers(nodo): if nodo == None: return 0 dfs(nodo, "", 0) return totalF def dfs(nodoAct, cadenaSuma, total): global totalF if(nodoAct.izquierda == None and nodoAct.derecha == None): total += int((cadenaSuma) + str(nodoAct.valor)) if(nodoAct.izquierda != None): dfs(nodoAct.izquierda, cadenaSuma+str(nodoAct.valor), total) if(nodoAct.derecha != None): dfs(nodoAct.derecha, cadenaSuma+str(nodoAct.valor), total) if totalF != total: totalF += total else: return totalF print(sum_numbers(nodo1)) ```totalF = 0 *class* <u>Node</u>:    *def* \_\_init\_\_(*self*, *valor*):        *self*.valor = *valor*        *self*.izquierda = None        *self*.derecha = None nodo1 = <u>Node</u>(1)nodo2 = <u>Node</u>(2)nodo3 = <u>Node</u>(3)nodo4 = <u>Node</u>(4)nodo5 = <u>Node</u>(5)nodo6 = <u>Node</u>(6) nodo1.izquierda = nodo2nodo1.derecha = nodo3nodo2.izquierda = nodo4nodo2.derecha = nodo5nodo3.izquierda = nodo6 *def* sum\_numbers(*nodo*):    if *nodo* == None:        return 0    dfs(*nodo*, "", 0)    return totalF *def* dfs(*nodoAct*, *cadenaSuma*, *total*):    global totalF    if(*nodoAct*.izquierda == None and *nodoAct*.derecha == None):        *total* += <u>int</u>(*(cadenaSuma)* + <u>str</u>(*nodoAct*.valor))    if(*nodoAct*.izquierda != None):        dfs(*nodoAct*.izquierda, *cadenaSuma*+<u>str</u>(*nodoAct*.valor), *total*)    if(*nodoAct*.derecha != None):        dfs(*nodoAct*.derecha, *cadenaSuma*+<u>str</u>(*nodoAct*.valor), *total*)    if totalF != *total*:     totalF += *total*    else: return totalF print(sum\_numbers(nodo1))    

Despues de pensar un poco lo logre


class Response:
    total = 0

    def __init__(self, total):
        self.total = total

    def dfs(self, node, valor_actual):
        parcial = valor_actual + str(node.valor)

        if node.izquierda is None and node.derecha is None:
            self.total = self.total + int(parcial)
        if node.derecha is not None:
            self.dfs(node.derecha, parcial)
        if node.izquierda is not None:
           self.dfs(node.izquierda, parcial)


def sum_numbers(node, valor_actual=''):
    response = Response(0)
    response.dfs(node, valor_actual)
    return response.total

Hola ūüėĄ, les comparto la soluci√≥n en Golang junto a la prueba.
.
solSRLN.go:

package main

import (
	"fmt"
	"strconv"
)

// Definición de la estructura del árbol
type Nodo struct {
	Val       int
	izquierda *Nodo
	derecha   *Nodo
}

// Creación del árbol
var arbolSRLN = &Nodo{
	Val: 1,
	izquierda: &Nodo{
		Val: 3,
		izquierda: &Nodo{
			Val:       5,
			izquierda: nil,
			derecha:   nil,
		},
		derecha: &Nodo{
			Val:       8,
			izquierda: nil,
			derecha:   nil,
		},
	},
	derecha: &Nodo{
		Val:       7,
		izquierda: nil,
		derecha: &Nodo{
			Val:       1,
			izquierda: nil,
			derecha:   nil,
		},
	},
}

// Funci√≥n que realiza la suma de los n√ļmeros del √°rbol
func sumNumbers(raiz *Nodo) int {
	if raiz == nil {
		return 0
	}
	total := 0
	dfs(raiz, "", &total)
	return total
}

// Funci√≥n DFS recursiva para recorrer el √°rbol y sumar los n√ļmeros
func dfs(raiz *Nodo, caminoActual string, sumaTotal *int) {
	if raiz.izquierda == nil && raiz.derecha == nil {
		valor, _ := strconv.Atoi(caminoActual + strconv.Itoa(raiz.Val))
		*sumaTotal += valor
	}
	if raiz.izquierda != nil {
		dfs(raiz.izquierda, caminoActual+strconv.Itoa(raiz.Val), sumaTotal)
	}
	if raiz.derecha != nil {
		dfs(raiz.derecha, caminoActual+strconv.Itoa(raiz.Val), sumaTotal)
	}
}

func main() {
	fmt.Println(sumNumbers(arbolSRLN))
}

.
Output:

Mi solucion en Python :

def sum_root_regresive(root):
    left = sum_function(root, 'left')
    right = sum_function(root, 'right')
    return left + right

def sum_function(root, direction, str_queue = ''):
    if root.get(direction) == None:
        return int(str_queue + str(root['value']))
    
    return sum_function(root[direction], direction, str_queue + str(root['value']))

Mi solución recursiva en python:

def sum_numbers(root: Node, start_number_with: str = '') -> int:
  if root.left is None and root.right is None:
    return int(start_number_with + str(root.value))
  
  left = 0
  right = 0
  
  if root.left is not None:
    left = sum_numbers(root.left, start_number_with + str(root.value))
  if root.right is not None:
    right = sum_numbers(root.right, start_number_with + str(root.value))

  
  return left + right