Encuentra al Ganador de la Solución LeetCode del Juego Circular

Declaración del problema Encuentre el ganador del juego circular Solución LeetCode: hay n amigos que están jugando un juego. Los amigos están sentados en círculo y están numerados del 1 al n en el sentido de las agujas del reloj. De manera más formal, moverse en el sentido de las agujas del reloj desde el enésimo amigo lo lleva al...

Lea más

Solución LeetCode transversal en orden de árbol binario

Declaración del problema: Recorrido en orden de árbol binario Solución de LeetCode Dada la raíz de un árbol binario, devolver el recorrido en orden de los valores de sus nodos. Ejemplo 1: Entrada: root = [1,null,2,3] Salida: [1,3,2] Ejemplo 2: Entrada: root = [] Salida: [] Ejemplo 3: Entrada: root = [1] Salida: [1] Restricciones: El número de nodos en...

Lea más

Solución Leetcode de suma mínima de ruta

Declaración del problema La solución de LeetCode de la suma mínima de la ruta: la "suma mínima de la ruta" dice que la cuadrícula anxm dada consta de números enteros no negativos y necesitamos encontrar una ruta desde la parte superior izquierda hasta la parte inferior derecha, lo que minimiza la suma de todos los números a lo largo de la ruta . Solo podemos movernos...

Lea más

Costo mínimo para subir escaleras Solución LeetCode

Declaración del problema Costo mínimo para subir escaleras Solución LeetCode: se proporciona un costo de matriz entera, donde costo[i] es el costo del iésimo escalón en una escalera. Una vez que pague el costo, puede subir uno o dos escalones. Puede comenzar desde el paso con el índice 0, o desde el paso con...

Lea más

Aplanar árbol binario a lista enlazada Solución LeetCode

Aplanar árbol binario a lista enlazada Solución LeetCode dice que – Dada la root de un árbol binario, aplane el árbol en una "lista enlazada":

  • La "lista enlazada" debe usar el mismo TreeNode clase donde el right puntero secundario apunta al siguiente nodo en la lista y el left el puntero hijo es siempre null.
  • La "lista enlazada" debe estar en el mismo orden que una Pedido Anticipado atravesar del árbol binario.

 

Ejemplo 1:

Aplanar árbol binario a lista enlazada Solución LeetCodeEntrada:

 root = [1,2,5,3,4,null,6]

Salida:

 [1,null,2,null,3,null,4,null,5,null,6]

Ejemplo 2:

Entrada:

 root = []

Salida:

 []

Ejemplo 3:

Entrada:

 root = [0]

Salida:

 [0]

 

ALGORITMO –

OCURRENCIA -

  • Para aplanar un árbol binario, primero encontraremos el elemento más a la derecha del subárbol izquierdo y después de obtener el elemento más a la derecha vincularemos el puntero derecho de ese nodo con un subárbol derecho de un árbol dado.
  • En el paso 2 vincularemos el puntero derecho del nodo raíz con el subárbol izquierdo y estableceremos el subárbol izquierdo como nulo.
  • En el paso 3, ahora nuestro nodo raíz es un nodo del subárbol derecho, el mismo proceso ocurrirá con este nodo y el proceso continuará hasta que todas las partes de la izquierda se vuelvan nulas.

Enfoque para Flatten Binary Tree to Linked List Solución de Leetcode –

– Al principio, ejecutaré un bucle, es decir, while (raíz! = nulo), luego tomaré dos variables y almacenaré el subárbol izquierdo.

– luego verificará el nodo más a la derecha del subárbol izquierdo usando while (k.left! = null) y vinculará ese nodo con el subárbol derecho usando (k.right = root.right).

– luego vincule el puntero derecho del nodo raíz con el subárbol izquierdo (root.right = left) y establezca el puntero izquierdo del nodo raíz como nulo (root.left=null) y se actualizará por (root = root.right) por lo que ahora la raíz es correcta nodo del subárbol.

– este proceso continuará hasta que todas las partes del subárbol izquierdo se conviertan en el subárbol derecho. Por lo tanto, el árbol binario se aplanará.

 

Aplanar árbol binario a lista enlazada Solución LeetCode

Aplanar árbol binario a lista enlazada Solución LeetCode

Solución Python:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

Solución Java:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

Complejidad del tiempo: O(N)

Complejidad espacial: O (1)

Como hemos atravesado una sola vez, la complejidad del tiempo estará o(n).

y como no hemos tomado ningún espacio extra, la complejidad del espacio será o(1) espacio extra constante.

Pregunta similar - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Insertar Borrar GetRandom O(1) Solución Leetcode

Declaración del problema La solución Insertar Eliminar GetRandom O(1) LeetCode: "Insertar Eliminar GetRandom O(1)" le pide que implemente estas cuatro funciones en la complejidad de tiempo O(1). insert(val): inserta el valor en el conjunto aleatorio y devuelve verdadero si el elemento está inicialmente ausente en el conjunto. Devuelve false cuando el...

Lea más

Solución de código de caché LRU

Declaración del problema La solución LRU Cache LeetCode: "LRU Cache" le pide que diseñe una estructura de datos que siga a la memoria caché LRU menos utilizada. Necesitamos implementar la clase LRUCache que tiene las siguientes funciones: LRUCache (capacidad int): inicializa la memoria caché LRU con capacidad de tamaño positivo. int get(int clave): Devuelve el valor...

Lea más

Eliminación mínima para hacer paréntesis válidos Solución LeetCode

Declaración del problema La eliminación mínima para hacer que los paréntesis sean válidos Solución de LeetCode: se le proporciona una cadena de '(', ')' y caracteres ingleses en minúsculas. Su tarea es eliminar el número mínimo de paréntesis ('(' o ')', en cualquier posición) para que la cadena de paréntesis resultante sea...

Lea más

Subcadena más larga sin caracteres repetidos Solución de Leetcode

Declaración del problema La subcadena más larga sin caracteres repetidos Solución LeetCode: establece que dada la cadena s. Necesitamos encontrar la subcadena más larga sin repetir caracteres. Ejemplo: Entrada: s = ”abcabcbb” Salida: 3 Explicación: La subcadena más larga sin caracteres repetidos tiene una longitud de 3. La cadena es: “abc”. Entrada: s = ”bbbbb” …

Lea más

Número de Fibonacci Solución LeetCode

Declaración del problema Número de Fibonacci Solución de LeetCode: el "Número de Fibonacci" establece que Los números de Fibonacci, comúnmente denotados como F (n), forman una secuencia, llamada secuencia de Fibonacci, de modo que cada número es la suma de los dos anteriores, a partir de 0 y 1 Es decir, F(0) = 0, F(1) = 1 F(n) = F(n – 1) + F(n …

Lea más

Translate »