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
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Implementación de Algoritmo DFS en Árboles Binarios con Golang
13/52¿Cómo se implementa un árbol binario en Golang?
Para los desarrolladores interesados en estructuras de datos, especialmente aquellos trabajando con Golang, crear y manejar un árbol binario es un ejercicio invaluable para mejorar las habilidades de codificación. Aquí abordaremos la implementación de un árbol binario en Go.
¿Qué es un nodo en un árbol binario y cómo se describe?
Un nodo en un árbol binario se configura con un valor y, generalmente, dos hijos: uno a la izquierda y otro a la derecha. En el contexto de Golang, puedes definir un nodo de la siguiente manera:
type Nodo struct {
Valor int
NodoIzquierdo *Nodo
NodoDerecho *Nodo
}
¿Cuál es la lógica para calcular el total de un árbol?
Al trabajar con un árbol binario, el objetivo puede ser, por ejemplo, calcular la suma de todos los caminos desde la raíz hasta las hojas. Este total iniciará en cero, y si la raíz es nula, simplemente retornamos cero.
var Total int = 0
func calcularTotal(raiz *Nodo) int {
if raiz == nil {
return 0
}
return Total
}
¿Cómo usar una función DFS para el cálculo de caminos?
Depth-First Search (DFS) es una técnica popular para explorar o recorrer estructuras de datos como grafos y árboles. En este contexto, creamos la función DFS que recibe el nodo actual del árbol, una cadena que representa el camino actual y el total hasta el momento.
func DFS(nodoActual *Nodo, caminoActual string, sumaTotal *int) {
if nodoActual.NodoIzquierdo == nil && nodoActual.NodoDerecho == nil {
*sumaTotal += convertirCaminoACadenaYASuma(caminoActual, nodoActual.Valor)
return
}
nuevoCamino := caminoActual + strconv.Itoa(nodoActual.Valor)
if nodoActual.NodoIzquierdo != nil {
DFS(nodoActual.NodoIzquierdo, nuevoCamino, sumaTotal)
}
if nodoActual.NodoDerecho != nil {
DFS(nodoActual.NodoDerecho, nuevoCamino, sumaTotal)
}
}
func convertirCaminoACadenaYASuma(camino string, valor int) int {
caminoCompleto := camino + strconv.Itoa(valor)
suma, _ := strconv.Atoi(caminoCompleto)
return suma
}
¿Por qué es importante realizar pruebas?
Es vital realizar pruebas, sobre todo si estás en un proceso de entrevista donde la precisión y la robustez del código son evaluadas. Las pruebas nos aseguran que la lógica y la solución planteada son correctas.
La importancia de las pruebas incluye:
- Validar la lógica: Asegurar que todos los caminos del árbol se calculan correctamente.
- Detectar errores: Permite identificar fallas antes de la ejecución de la lógica en situaciones reales.
¿Cómo se pueden realizar pruebas de escritorio o unitarias?
Antes de ejecutar pruebas unitarias automáticas, es clave realizar pruebas de escritorio. Esto implica verificar el resultado esperado paso a paso manualmente. Además, define funciones de prueba en tu código que verifiquen los resultados contra casos de prueba conocidos.
Invito a los lectores a involucrarse practicando crear varias estructuras de árbol y explorando diferentes algoritmos. Comenten su experiencia o compartan cualquier error que hayan encontrado y cómo lo corrigieron. ¡La programación es una habilidad en constante perfeccionamiento!
Aportes 16
Preguntas 1
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;
}
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);
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
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?