Pokyny krok za krokom od uzla binárneho stromu k inému riešeniu LeetCode

Vyhlásenie o probléme: Pokyny krok za krokom Od uzla binárneho stromu k inému riešeniu LeetCode – Dostali ste koreň binárneho stromu s n uzlami. Každý uzol má jednoznačne priradenú hodnotu od 1 do n. Dostanete tiež celé číslo štartValue predstavujúce hodnotu počiatočného uzla s a iné celé číslo destValue predstavujúce hodnotu cieľa ...

Čítaj viac

Vertikálne poradie prechodu binárneho stromu riešenia LeetCode

Vyhlásenie o probléme Prechod vertikálneho poradia binárneho stromu Riešenie LeetCode hovorí – Vzhľadom na koreň binárneho stromu vypočítajte vertikálny prechod binárneho stromu. Pre každý uzol na pozícii (riadok, stĺpec) budú jeho ľavé a pravé potomky na pozíciách (riadok + 1, stĺpec – 1) a (riadok + 1, stĺpec + 1). …

Čítaj viac

Riešenie LeetCode odmocnina súčtu do počtu listov

Vyhlásenie o probléme Čísla súčtu odmocnina do listu LeetCode riešenie hovorí – Dostali ste koreň binárneho stromu, ktorý obsahuje iba číslice od 0 do 9. Každá cesta od koreňa po list v strome predstavuje číslo. Napríklad cesta od koreňa po list 1 -> 2 -> 3 predstavuje číslo 123. Vráti celkový súčet všetkých čísel od koreňa po list. Test…

Čítaj viac

Binárne Tree Inorder Traversal LeetCode riešenie

Problém: Binary Tree Inorder Traversal LeetCode riešenie Vzhľadom na koreň binárneho stromu vráťte inorder traversal hodnôt jeho uzlov. Príklad 1: Vstup: root = [1,null,2,3] Výstup: [1,3,2] Príklad 2: Vstup: root = [] Výstup: [] Príklad 3: Vstup: root = [1] Výstup: [1] Obmedzenia: Počet uzlov v…

Čítaj viac

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

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:

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCodevstup:

 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í.

 

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

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

Najnižší spoločný predok riešenia Leetcode Binary Tree

Vyhlásenie o probléme Najnižší spoločný predok binárneho stromu Riešenie LeetCode – „Najnižší spoločný predok binárneho stromu“ uvádza, že vzhľadom na koreň binárneho stromu a dva uzly stromu. Musíme nájsť najnižšieho spoločného predka týchto dvoch uzlov. Najnižšie bežné…

Čítaj viac

Vyplnenie ďalších pravých ukazovateľov v každom riešení Leetcode uzla

Vyhlásenie o probléme Vyplnenie ďalších pravých ukazovateľov v každom uzle Riešenie LeetCode – „Vyplnenie ďalších pravých ukazovateľov v každom uzle“ uvádza, že vzhľadom na koreň dokonalého binárneho stromu a musíme vyplniť každý ďalší ukazovateľ uzla na jeho ďalší pravý uzol. Ak nie je ďalšia…

Čítaj viac

Odstrániť uzly a vrátiť riešenie Forest Leetcode

Vyhlásenie o probléme Riešenie LeetCode Delete Nodes and Return Forest – „Vymazať uzly a vrátiť les“ uvádza, že vzhľadom na koreň binárneho stromu má každý uzol odlišnú hodnotu. Máme tiež pole to_delete, kde potrebujeme vymazať všetky uzly s hodnotami obsiahnutými v ...

Čítaj viac

Obnovte riešenie Leetcode Binary Search Tree

Vyhlásenie o probléme Riešenie LeetCode Recover Binary Search Tree – „Recover Binary Search Tree“ uvádza, že vzhľadom na koreň binárneho vyhľadávacieho stromu, kde sú omylom zamenené hodnoty presne dvoch uzlov. Musíme obnoviť strom bez zmeny jeho štruktúry. Príklad: Vstup: root = [1,3,null,null,2] Výstup: [3,1,null,null,2] …

Čítaj viac

Translate »