Kotlin Binary Tree Preorder Traversal (una solución recursiva y sin usar recursividad)

Esta publicación trata sobre el recorrido en orden previo de un árbol binario, un método para recorrer el árbol en el que se visita el nodo actual antes que sus hijos. El algoritmo transversal de preorden visita primero el nodo raíz, luego visita recursivamente el subárbol izquierdo, seguido por el subárbol derecho. El resultado de un recorrido en orden previo es una lista de los valores de los nodos en el orden en que se visitan. Esta publicación lo ayudará a comprender cómo atravesar un árbol binario y también cómo implementarlo de diferentes maneras.

El recorrido en orden anticipado es un método para recorrer un árbol binario en el que se visita el nodo actual antes que sus hijos. El algoritmo visita primero el nodo raíz, luego visita recursivamente el subárbol izquierdo, seguido por el subárbol derecho. El resultado de un recorrido en orden previo es una lista de los valores de los nodos en el orden en que se visitan.

En este problema, se le da la raíz de un árbol binario representado por la clase TreeNode en Kotlin, que tiene una propiedad val para el valor del nodo y propiedades left y right para sus hijos izquierdo y derecho, respectivamente. Su tarea es escribir dos implementaciones de una función que realice un recorrido en orden previo del árbol binario y devuelva una lista de los valores de los nodos. Uno debe ser una solución recursiva y el otro no debe usar la recursividad.

Aquí está la firma de clase de la función:

 fun preorderTraversal(root: TreeNode?): List<Int>

La entrada a la función es el nodo raíz del árbol binario, y la salida es una lista de números enteros que representan los valores de los nodos en el orden en que se visitan durante el recorrido previo al pedido.

Descripciones:

Dada la raíz de un árbol binario, devuelva el recorrido de preorden de los valores de sus nodos. Haga esto con una solución recursiva y sin usar la recursividad.

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

Aquí hay una solución recursiva al problema:

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

Esta función realiza un recorrido de preorden del árbol binario y devuelve una lista de los valores de los nodos en el orden en que se visitan.

El algoritmo funciona de la siguiente manera:

1. Si el nodo raíz es nulo, devuelve una lista vacía.
2. Agregue el valor del nodo raíz a la lista de resultados.
3. Atraviese recursivamente el subárbol izquierdo llamando a la función en el hijo izquierdo de la raíz y agregue la lista devuelta a la lista de resultados.
4. Atraviese recursivamente el subárbol derecho llamando a la función en el hijo derecho de la raíz y agregue la lista devuelta a la lista de resultados.
5. Devuelve la lista de resultados.

Este algoritmo tiene una complejidad temporal de O(n), donde n es el número de nodos en el árbol, y una complejidad espacial de O(h), donde h es la altura del árbol (debido a la pila de llamadas).

Aquí hay una solución que usa un enfoque iterativo (es decir, sin usar la recursividad):

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

Esta función realiza un recorrido de preorden del árbol binario y devuelve una lista de los valores de los nodos en el orden en que se visitan. Utiliza una pila para realizar un seguimiento de los nodos que aún deben visitarse.

El algoritmo funciona de la siguiente manera:

1. Inicialice una pila vacía y establezca el nodo actual en la raíz del árbol.

2. Mientras que el nodo actual no es nulo o la pila no está vacía:

   1. Si bien el nodo actual no es nulo:

      1. Agregue el valor del nodo actual a la lista de resultados.
      2. Inserte el nodo actual en la pila.
      3. Establece el nodo actual en su hijo izquierdo.

   2. Extraiga el nodo superior de la pila y establezca el nodo actual en su hijo derecho.

3. Devuelve la lista de resultados.

Este algoritmo tiene una complejidad temporal de O(n), donde n es el número de nodos del árbol, y una complejidad espacial de O(h), donde h es la altura del árbol.

¡Espero que esto ayude! Avíseme si tiene alguna otra pregunta.