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

Je graf bipartitný? Riešenie LeetCode

Problémové vyhlásenie je graf Bipartite LeetCode Riešenie- Existuje neorientovaný graf s n uzlami, kde každý uzol je očíslovaný medzi 0 a n – 1. Dostanete 2D graf poľa, kde graph[u] je pole uzlov, ktoré uzol u susedí s. Formálnejšie, pre každé v v grafe[u] existuje medzi uzlom u a uzlom v neorientovaná hrana. Graf má …

Čítaj viac

Navrhnite pridávanie a vyhľadávanie slov dátovú štruktúru Riešenie LeetCode

Vyhlásenie o probléme: Navrhnite dátovú štruktúru pridávania a vyhľadávania slov Riešenie LeetCode hovorí – Navrhnite dátovú štruktúru, ktorá podporuje pridávanie nových slov a zistenie, či sa reťazec zhoduje s predtým pridaným reťazcom. Implementujte triedu WordDictionary: WordDictionary() Inicializuje objekt. void addWord(word) Pridá slovo do dátovej štruktúry, môže byť spárované neskôr. bool search(word) Vráti hodnotu true, ak existuje…

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

Translate »