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

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

Recuperar árbol de búsqueda binario Solución Leetcode

Declaración del problema La solución de LeetCode del árbol de búsqueda binaria de recuperación: "Recuperar el árbol de búsqueda binaria" establece que dada la raíz del árbol de búsqueda binaria, donde los valores de exactamente dos nodos se intercambian por error. Necesitamos recuperar el árbol sin cambiar su estructura. Ejemplo: Entrada: root = [1,3,null,null,2] Salida: [3,1,null,null,2] …

Lea más

Solución de Leetcode de árbol simétrico

Declaración del problema La solución LeetCode del árbol simétrico: el "árbol simétrico" establece que, dada la raíz del árbol binario, debemos verificar si el árbol binario dado es un espejo de sí mismo (simétrico alrededor de su centro) o no. En caso afirmativo, debemos devolver verdadero; de lo contrario, falso. Ejemplo: …

Lea más

Translate »