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

• „Povezana lista“ treba da koristi isto TreeNode razred u kojem je right dijete pokazivač pokazuje na sljedeći čvor na listi i left dijete pokazivač je uvijek null.
• „Povezana lista“ treba da bude u istom redosledu kao a pred-porudžbina prelazak binarnog stabla.

 

Primer 1:

Ulaz:

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

Izlaz:

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

Primer 2:

Ulaz:

 root = []

Izlaz:

 []

Primer 3:

Ulaz:

 root = [0]

Izlaz:

 [0]

 

ALGORITAM –

IDEJA –

• Da 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 sa desnim podstablom datog stabla.
• U koraku 2 ćemo povezati desni pokazivač korijenskog čvora sa lijevim podstablom i postaviti lijevo podstablo kao null.
• U koraku 3 sada je naš korijenski čvor čvor desnog podstabla, isti proces će se dogoditi sa 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), zatim ću uzeti dvije varijable i pohraniti lijevo podstablo.

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

– zatim povežite desni pokazivač korijenskog čvora sa 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, vremenska složenost će biti o(n).

i kako nismo uzeli nikakav dodatni prostor, kompleksnost prostora će biti o(1) konstantan dodatni prostor.

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