Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCode dice chì – Data u root di un arbre binariu, appiattite l'arburu in una "lista ligata":

• A "lista ligata" deve aduprà u listessu TreeNode classe induve u right puntatore di u zitellu punta à u prossimu node in a lista è u left puntatore zitellu hè sempre null.
• A "lista ligata" deve esse in u listessu ordine cum'è a pre-ordine traversu di l'arburu binariu.

 

Esemplariu 1:

Input:

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

Output:

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

Esemplariu 2:

Input:

 root = []

Output:

 []

Esemplariu 3:

Input:

 root = [0]

Output:

 [0]

 

ALGORITMU -

IDEA -

• Per appiattà un arbulu binariu, truvemu prima l'elementu rightmost di u subtree left è dopu avè ottenutu l'elementu rightmost, ligheremu u punter right-pointer di quellu node cù un subtree right di un arbulu datu.
• In u passu 2 ligaremu u punteru dirittu di u node radicali cù u subtree left è stabilisce u subtree left cum'è null.
• In u passu 3 avà u nostru node radicali hè un nodu subtree right u stessu prucessu accadrà cù questu node è u prucessu continuarà sempre finu à chì tutte e parte manca diventanu nulle.

Approcciu per Flatten Binary Tree to Linked List Soluzione Leetcode -

– À u principiu, eseguiraghju un loop, vale à dì while(root != null) dopu piglià duie variàbili è almacenà u subtree left.

- dopu verificarà u nodu più à destra di u subtree left usendu while (k.left != null) è ligà quellu node cù u subtree right usendu (k.right = root.right).

- poi ligà u puntatore right di u nodu radicale cù u subtree left (root.right = left) è stabilisce u puntatore left di u node root cum'è null (root.left = null) è aghjurnerà da (root = root.right) cusì avà a radica hè ghjustu. node subtree.

- stu prucessu hà da cuntinuà finu à chì tutte e parti di u subtree di manca diventanu subtree right. Dunque, l'arbulu binariu sarà appiattitu.

 

Soluzione 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

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

A cumplessità di u tempu: O(N)

Cumplessità Spaziale: O (1)

Cumu avemu traversatu una sola volta, a cumplessità di u tempu serà o (n).

è cum'è ùn avemu micca pigliatu un spaziu extra, a cumplessità di u spaziu serà o (1) spaziu extra constantu.

Domanda simile - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm