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:

Entrada:

 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á.

 

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