Clase 13 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
JOSE EMMANUEL RAMIREZ GUERRERO
JOHANBERT MOSQUERA
Miguel Angel Reyes Moreno
Andres Silva Vega
Usuario anónimo
Tomás Santa Cruz
Leandro Ayala
Rubén Cocoletzi Mata
Santiago Muñoz
Nicolas Lopez
Kellbis Salazar
Platzi
John Eduard Meneses González
Michael Martinez
Carlos Guzman
REYNALDO FABIAN NORIEGA ZAMBRANO
Cristian Toro
Miguel Angel Reyes Moreno
Hans Arias
Alexander Palazuelos
Daniel Ortiz
Harold Zurita Simon
German Lozickyj
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 }
No hay solucion que alguien hiciera en JS Javascript? :( jaja en cuanto pueda la hago y la subo jeje
Tarde pero seguro:
// Definition for a binary tree node.
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
sumNumbers(root) {
const dfs = (node, currentNumber) => {
if (!node) {
return 0;
}
currentNumber = currentNumber * 10 + node.val;
if (!node.left && !node.right) {
return currentNumber;
}
return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
};
return dfs(root, 0);
}
}
// Example usage:
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
const solution = new Solution();
const result = solution.sumNumbers(root1);
console.log(result: ${result});
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; }
Puede ser que el error en el codigo es que la variable caminoActual nunca se regenera?
Esta es mi solucion con C++23
#include <print> typedef struct Nodo { int val; Nodo *left; Nodo *right; Nodo(int x) : val(x), left(nullptr), right(nullptr) {} } Nodo; int sumOfNumber(Nodo *raiz, int acc) { if (raiz == nullptr) return 0; int current = acc * 10 + raiz->val; if (raiz->left == nullptr && raiz->right == nullptr) return current; return sumOfNumber(raiz->left, current) + sumOfNumber(raiz->right, current); } int sumRootToLeaf(Nodo *raiz) { return sumOfNumber(raiz, 0); } int main() { Nodo *raiz = new Nodo(1); raiz->left = new Nodo(2); raiz->left->left = new Nodo(4); raiz->right = new Nodo(3); std::print("Sum is {}\n", sumRootToLeaf(raiz)); // Output: 25 return 0; }
Solución en Python para arbol eneario:
class Node: def __init__(self, value, child=None): self.value = value self.child = child or [] graph = Node( 1, [ Node(3, [Node(5), Node(8)]), Node(7, [Node(1)]) ] ) def sumRootToLeafDfs(graph): stack = [{ "node": graph, "currentSum": graph.value }] total = 0 while stack: current = stack.pop() node = current["node"] currentSum = current["currentSum"] if not len(node.child): print(f"Root to leaf -> {currentSum}") total += int(currentSum) else: for child in reversed(node.child): stack.append({ "node": child, "currentSum": currentSum * 10 + child.value }) print(f"Total root to leaf -> {total}") sumRootToLeafDfs(graph=graph)
Mi solucion en Java:public static int treePathSum(NodeTree root, int sum){ if (root == null){return 0;}
// Update the value. sum * 10 to move forward the digit at 1, then + the root.val. sum = sum * 10 + root.val;
// If there isn't more node (leaf node), then return the sum. if(root.left == null && root.right == null){ //System.out.println("root.value -> " + root.val + " sum -> " + sum); return sum; }
// Recursion instead of uses a Stack for iteration. return treePathSum(root.left, sum) + treePathSum(root.right, sum); }
public static int treePathSum(NodeTree root, int sum){ if (root == null){return 0;} // Update the value. sum * 10 to move forward the digit at 1, then + the root.val. sum = sum * 10 + root.val; // If there isn't more node (leaf node), then return the sum. if(root.left == null && root.right == null){ //System.out.println("root.value -> " + root.val + " sum -> " + sum); return sum; } // Recursion instead of uses a Stack for iteration. return treePathSum(root.left, sum) + treePathSum(root.right, sum); }
Que sentido tiene hacer ese codigo y no testear a ver si funciona?
Lo que busca la instrucción es enseñar cómo implementar una solución al problema de generar combinaciones a partir de un número de teléfono, usando programación recursiva y brindar la oportunidad de reflexionar sobre la complejidad del algoritmo.
My solution!!
Siendo sincero la explicación es muy confusa o no cuenta con cualidades para enseñar.
Mi solucion recursiva y enearia con python.
def dfs(root, current_number=''): if not root.get('children', False): print(current_number) return [current_number] results = [] for child in root.get('children', []): new_number = f'{current_number}{child.get('value')}' result = dfs(child, new_number) results.extend(result) return results def sum_root_leaf_number(root): numbers_result = dfs(root, str(root.get('value'))); result = 0 for number in numbers_result: result += int(number) return result ```Data de ejemplo: ```js graph_short = { 'value': 1, 'children': [ { 'value': 2, 'children': [ {'value': 3} ] }, { 'value': 2, 'children': [ {'value': 3} ] } ] }
Mi implementacion en C++:
#include<iostream> using namespace std; class Node{ public: int val; Node *leftNode; Node *rightNode; Node(int val, Node *leftNode, Node *rightNode){ this->val = val; this->leftNode = leftNode; this->rightNode = rightNode; } }; void addValues(Node *root, int &total, int current){ if(!root) return; current = 10*current + root->val; if(!root->leftNode && !root->rightNode){ total += current; } if(root->leftNode){ addValues(root->leftNode, total, current); } if(root->rightNode){ addValues(root->rightNode, total, current); } } int main(){ int total = 0; int current = 0; Node *node5 = new Node(5, NULL, NULL); Node *node8 = new Node(8, NULL, NULL); Node *node7 = new Node(7, NULL, NULL); Node *node3 = new Node(3, node5, node8); Node *node2 = new Node(2, node7, NULL); Node *bT = new Node(1, node3, node2); addValues(bT, total, current); cout << "total = " << total << endl; return 0; }
Solución en Python
def Sum_Root(nodo): if not nodo: return 0 return dfs(nodo) def dfs(nodo , caminoActual=""): if not nodo.izquierda and not nodo.derecha: return int(caminoActual + str(nodo.valor)) total = 0 if nodo.izquierda: total += dfs(nodo.izquierda , caminoActual + str(nodo.valor)) if nodo.derecha: total += dfs(nodo.derecha , caminoActual + str(nodo.valor)) return total
Código un poco más simplificado:
package main import ( "fmt") // TreeNode represents a node in a binary tree.type TreeNode struct { Val int Left *TreeNode Right *TreeNode} // sumNumbers function calculates the sum of all numbers formed by root-to-leaf paths.func sumNumbers(root *TreeNode) int { var dfs func(node *TreeNode, currentNumber int) int dfs = func(node *TreeNode, currentNumber int) int { if node == nil { return 0 } currentNumber = currentNumber*10 + node.Val if node.Left == nil && node.Right == nil { return currentNumber } return dfs(node.Left, currentNumber) + dfs(node.Right, currentNumber) } return dfs(root, 0)} func main() { // Example usage: root := &TreeNode{Val: 1} root.Left = &TreeNode{Val: 2} root.Right = &TreeNode{Val: 3} result := sumNumbers(root) fmt.Printf("result: %d\n", result)}
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.
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']))
