Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode hovorí, že – Vzhľadom na root binárneho stromu, vyrovnajte strom do „prepojeného zoznamu“:

• „Prepojený zoznam“ by mal používať to isté TreeNode trieda, kde right podriadený ukazovateľ ukazuje na nasledujúci uzol v zozname a left dieťa ukazovateľ je vždy null.
• „Prepojený zoznam“ by mal byť v rovnakom poradí ako a pre-order priechod binárneho stromu.

 

Príklad 1:

vstup:

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

Výkon:

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

Príklad 2:

vstup:

 root = []

Výkon:

 []

Príklad 3:

vstup:

 root = [0]

Výkon:

 [0]

 

ALGORITHM –

NÁPAD -

• Aby sme sploštili binárny strom, najskôr nájdeme prvok ľavého podstromu úplne vpravo a potom, čo dostaneme prvok úplne vpravo, spojíme pravý ukazovateľ tohto uzla s pravým podstromom daného stromu.
• V kroku 2 prepojíme pravý ukazovateľ koreňového uzla s ľavým podstromom a ľavý podstrom nastavíme na hodnotu null.
• V kroku 3 je teraz náš koreňový uzol uzol pravého podstromu rovnaký proces sa stane s týmto uzlom a proces bude pokračovať, kým sa všetky ľavé časti nestanú nulovými.

Prístup k vyrovnávaniu binárneho stromu k riešeniu prepojeného zoznamu Leetcode –

– Najprv spustím cyklus, tj while(root != null), potom vezmem dve premenné a uložím ľavý podstrom.

– potom pomocou while(k.left != null) skontroluje uzol ľavého podstromu úplne vpravo a pomocou (k.right = root.right) prepojí tento uzol s pravým podstromom.

– potom prepojte pravý ukazovateľ koreňového uzla s ľavým podstromom (root.right = vľavo) a nastavte ľavý ukazovateľ koreňového uzla ako null (root.left=null) a aktualizuje sa o ( root = root.right ), takže teraz má root pravdu uzol podstromu.

– tento proces bude pokračovať, kým sa všetky časti ľavého podstromu nestanú pravým podstromom. Preto sa binárny strom sploští.

 

Riešenie 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

Java riešenie:

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

Časová zložitosť: O(N)

Zložitosť vesmíru: O (1)

Keďže sme prešli iba raz, časová zložitosť bude o(n).

a keďže sme nezobrali žiadny priestor navyše, zložitosť priestoru bude o (1) konštantný priestor navyše.

Podobná otázka - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm