Recorrido de orden vertical de árbol binario Solución LeetCode

Declaración del problema Recorrido de orden vertical del árbol binario La solución de LeetCode dice: Dada la raíz de un árbol binario, calcule el recorrido de orden vertical del árbol binario. Para cada nodo en la posición (fila, columna), sus hijos izquierdo y derecho estarán en las posiciones (fila + 1, columna - 1) y (fila + 1, columna + 1) respectivamente. …

Lea más

Sumar números de raíz a hoja Solución LeetCode

Declaración del problema Suma de la raíz a los números de hoja La solución de LeetCode dice: se le da la raíz de un árbol binario que contiene dígitos del 0 al 9 únicamente. Cada ruta de raíz a hoja en el árbol representa un número. Por ejemplo, la ruta de raíz a hoja 1 -> 2 -> 3 representa el número 123. Devuelve la suma total de todos los números de raíz a hoja. Prueba …

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

¿El grafo es bipartito? Solución LeetCode

El enunciado del problema es una solución bipartita de código LeetCode gráfico: hay un gráfico no dirigido con n nodos, donde cada nodo está numerado entre 0 y n – 1. Se le proporciona un gráfico de matriz 2D, donde el gráfico [u] es una matriz de nodos que nodo u es adyacente a. Más formalmente, para cada v en el gráfico[u], hay una arista no dirigida entre el nodo u y el nodo v. El gráfico tiene...

Lea más

Diseño Agregar y buscar palabras Estructura de datos Solución LeetCode

Declaración del problema: diseñar una estructura de datos de agregar y buscar palabras La solución de LeetCode dice: diseñe una estructura de datos que admita agregar nuevas palabras y encontrar si una cadena coincide con cualquier cadena agregada previamente. Implemente la clase WordDictionary: WordDictionary() Inicializa el objeto. void addWord(palabra) Agrega una palabra a la estructura de datos, se puede comparar más tarde. bool buscar(palabra) Devuelve verdadero si hay...

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

El ancestro común más bajo de un árbol binario Solución Leetcode

Declaración del problema El antepasado común más bajo de un árbol binario Solución de LeetCode: "El antepasado común más bajo de un árbol binario" establece que dada la raíz del árbol binario y dos nodos del árbol. Necesitamos encontrar el ancestro común más bajo de estos dos nodos. El mínimo común…

Lea más

Rellenar los punteros siguientes a la derecha en cada nodo Solución de Leetcode

Declaración del problema Poblar los punteros siguientes a la derecha en cada nodo Solución de LeetCode: "Poblar los punteros siguientes a la derecha en cada nodo" establece que, dada la raíz del árbol binario perfecto, necesitamos llenar cada puntero siguiente del nodo a su siguiente nodo derecho. Si no hay siguiente...

Lea más

Eliminar nodos y devolver la solución Forest Leetcode

Declaración del problema La solución de LeetCode para eliminar nodos y devolver el bosque: "Eliminar nodos y devolver el bosque" establece que dada la raíz del árbol binario donde cada nodo tiene un valor distinto. También tenemos una matriz, to_delete, donde necesitamos eliminar todos los nodos con valores contenidos en...

Lea más

Translate »