Poravnajte binarno stablo na povezani popis LeetCode rješenje kaže da – S obzirom na root binarnog stabla, poravnajte stablo u "povezani popis":

• "Povezani popis" trebao bi koristiti isto TreeNode razred gdje se right dijete pokazivač pokazuje na sljedeći čvor na popisu i left dječji pokazivač je uvijek null.
• "Povezani popis" trebao bi biti istim redoslijedom kao a unaprijed naručiti prijelaz binarnog stabla.

 

Primjer 1:

Ulazni:

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

Izlaz:

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

Primjer 2:

Ulazni:

 root = []

Izlaz:

 []

Primjer 3:

Ulazni:

 root = [0]

Izlaz:

 [0]

 

ALGORITAM –

IDEJA –

• Kako bismo izravnali binarno stablo, prvo ćemo pronaći krajnji desni element lijevog podstabla, a nakon što dobijemo krajnji desni element povezat ćemo desni pokazivač tog čvora s desnim podstablom danog stabla.
• U koraku 2 povezat ćemo desni pokazivač korijenskog čvora s lijevim podstablom i postaviti lijevo podstablo kao null.
• U koraku 3 sada je naš korijenski čvor čvor desnog podstabla, isti proces će se dogoditi s ovim čvorom i proces će se nastaviti sve dok svi lijevi dijelovi ne postanu nulti.

Pristup za izravnavanje binarnog stabla na povezanu listu Leetcode rješenje –

– Prvo ću pokrenuti petlju, tj. while(root != null), a zatim ću uzeti dvije varijable i pohraniti lijevo podstablo.

– zatim će provjeriti krajnji desni čvor lijevog podstabla korištenjem while(k.left != null) i povezati taj čvor s desnim podstablom koristeći (k.right = root.right).

– zatim povežite desni pokazivač korijenskog čvora s lijevim podstablom (root.right = lijevo) i postavite lijevi pokazivač korijenskog čvora kao null(root.left=null) i ažurirat će se za ( root = root.right ) tako da je sada root udesno čvor podstabla.

– ovaj proces će se nastaviti sve dok svi dijelovi lijevog podstabla ne postanu desno podstablo. Dakle, binarno stablo će se spljoštiti.

 

Python rješenje:

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

Java rješenje:

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

Vremenska složenost: O(N)

Složenost prostora: O (1)

Kako smo prošli samo jednom, složenost vremena bit će o(n).

a kako nismo uzeli nikakav dodatni prostor, složenost prostora bit će o(1) konstantni dodatni prostor.

Slično pitanje - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm