Aplanar a árbore binaria á lista ligada Solución LeetCode di que – Dado o root dunha árbore binaria, aplana a árbore nunha "lista ligada":

• A "lista vinculada" debería usar o mesmo TreeNode clase onde o right o punteiro fillo apunta ao seguinte nodo da lista e o left o punteiro fillo é sempre null.
• A "lista vinculada" debe estar na mesma orde que a pre-orde travesía da árbore binaria.

 

Exemplo 1:

Entrada:

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

saída:

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

Exemplo 2:

Entrada:

 root = []

saída:

 []

Exemplo 3:

Entrada:

 root = [0]

saída:

 [0]

 

ALGORITMO -

IDEA -

• Para aplanar unha árbore binaria, primeiro atoparemos o elemento máis á dereita da subárbore esquerda e despois de obter o elemento máis á dereita vincularemos o punteiro dereito dese nodo cunha subárbore dereita dunha determinada árbore.
• No paso 2 vincularemos o punteiro dereito do nodo raíz coa subárbore esquerda e estableceremos a subárbore esquerda como nula.
• No paso 3 agora o noso nodo raíz é un nodo da subárbore dereita, o mesmo proceso ocorrerá con este nodo e o proceso aínda continuará ata que todas as partes da esquerda se volvan nulas.

Enfoque para aplanar a árbore binaria á lista ligada Solución Leetcode -

– Ao principio, executarei un bucle, é dicir, while(raíz != nulo) despois tomarei dúas variables e almacenarei a subárbore esquerda.

– entón comprobará o nodo máis dereito da subárbore esquerda usando while(k.left != null) e vinculará ese nodo coa subárbore dereita usando (k.right = root.right).

– A continuación, ligue o punteiro dereito do nodo raíz coa subárbore esquerda (root.right = left) e configure o punteiro esquerdo do nodo raíz como nulo (root.left=null) e actualizarase por (root = root.right) polo que agora root é correcto nodo da subárbore.

– este proceso continuará ata que todas as partes da subárbore esquerda se convertan na subárbore dereita. Polo tanto, a árbore binaria quedará aplanada.

 

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;
        }
    }
}

Complexidade temporal: O(N)

Complexidade espacial: O (1)

Como só percorremos unha vez, a complexidade do tempo será o(n).

e como non ocupamos ningún espazo extra, a complexidade do espazo será o(1) espazo extra constante.

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