Puntuación de Paréntesis Solución LeetCode

Declaración del problema La puntuación de la solución LeetCode de paréntesis dice: dada una cadena de paréntesis equilibrada s y devolver la puntuación máxima. La puntuación de una cadena de paréntesis equilibrada se basa en las siguientes reglas: “()” tiene una puntuación de 1. AB tiene una puntuación A + B, donde A y B son cadenas de paréntesis equilibradas. (A) tiene una puntuación de 2 * A, donde A es un...

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 de Leetcode de cadena de decodificación

Declaración del problema La solución LeetCode de cadena de decodificación: "Cadena de decodificación" le pide que convierta la cadena codificada en una cadena decodificada. La regla de codificación es k[cadena_codificada], donde la cadena_codificada dentro de los corchetes se repite exactamente k veces, donde k es un número entero positivo. Ejemplo: Entrada: s = ”3[a]2[bc]” Salida: “aaabcbc” …

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

Añadir dos números II Solución Leetcode

Declaración del problema La solución LeetCode Suma dos números II: "Suma dos números II" establece que dos listas enlazadas no vacías representan dos enteros no negativos donde el dígito más significativo viene primero y cada nodo contiene exactamente un dígito. Necesitamos sumar los dos números y devolver la suma como...

Lea más

Temperaturas Diarias Solución Leetcode

Declaración del problema La solución de Leetcode de temperaturas diarias: establece que dada una matriz de temperaturas enteras que representan las temperaturas diarias, devuelve una respuesta de matriz tal que la respuesta [i] es la cantidad de días que debe esperar después del i-ésimo día para obtener una temperatura más cálida. Si no hay un día futuro para el cual esto sea posible, mantenga answer[i] == 0 en su lugar. …

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

Solución Leetcode para atrapar agua de lluvia

Declaración del problema La solución de LeetCode para atrapar el agua de lluvia: "Atrapar el agua de lluvia" establece que dada una matriz de alturas que representa un mapa de elevación donde el ancho de cada barra es 1. Necesitamos encontrar la cantidad de agua atrapada después de la lluvia. Ejemplo: Entrada: altura = [0,1,0,2,1,0,1,3,2,1,2,1] Salida: 6 Explicación: Comprobar...

Lea más

Paréntesis Válidos Solución Leetcode

Declaración del problema La solución LeetCode de paréntesis válidos: los "paréntesis válidos" indican que se le da una cadena que contiene solo los caracteres '(', ')', '{', '}', '[' y ']'. Necesitamos determinar si la cadena de entrada es una cadena válida o no. Se dice que una cadena es una cadena válida si los corchetes abiertos deben cerrarse...

Lea más

Solución Leetcode de pila de frecuencia máxima

Declaración del problema La solución LeetCode de pila de frecuencia máxima: "Pila de frecuencia máxima" le pide que diseñe una pila de frecuencia en la que cada vez que sacamos un elemento de la pila, debe devolver el elemento más frecuente presente en la pila. Implemente la clase FreqStack: FreqStack() construye una pila de frecuencia vacía. void push(int val) empuja …

Lea más

Translate »