Zbroj korijena listova brojeva LeetCode rješenje

Najava problema Sum Root to Leaf Numbers LeetCode Rješenje kaže – Dat vam je korijen binarnog stabla koje sadrži samo cifre od 0 do 9. Svaka staza od korijena do lista u stablu predstavlja broj. Na primjer, putanja od korijena do lista 1 -> 2 -> 3 predstavlja broj 123. Vrati ukupan zbir svih brojeva od korijena do lista. Test…

Čitaj više

Binarno stablo Inorder Traversal LeetCode rješenje

Iskaz problema: Binarno stablo Inorder Traversal LeetCode rješenje Dati korijen binarnog stabla, vratite prelazak u redoslijedu vrijednosti njegovih čvorova. Primjer 1: Ulaz: root = [1,null,2,3] Izlaz: [1,3,2] Primjer 2: Ulaz: root = [] Izlaz: [] Primjer 3: Ulaz: root = [1] Izlaz: [1] Ograničenja: broj čvorova u…

Čitaj više

Poravnajte binarno stablo na povezanu listu LeetCode rješenje

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:

Poravnajte binarno stablo na povezanu listu LeetCode rješenjeUlaz:

 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.

 

Poravnajte binarno stablo na povezanu listu LeetCode rješenje

Poravnajte binarno stablo na povezanu listu LeetCode rješenje

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

Najniži zajednički predak rješenja Leetcode binarnog stabla

Iskaz problema Najniži zajednički predak binarnog stabla LeetCode rješenje – “Najniži zajednički predak binarnog stabla” navodi da je dat korijen binarnog stabla i dva čvora stabla. Moramo pronaći najnižeg zajedničkog pretka ova dva čvora. Najniži uobičajeni…

Čitaj više

Popunjavanje sljedećih desnih pokazivača u svakom čvornom Leetcode rješenju

Iskaz problema Popunjavanje sljedećih desnih pokazivača u svakom čvoru LeetCode rješenje – “Popunjavanje sljedećih desnih pokazivača u svakom čvoru” navodi da je s obzirom na korijen savršenog binarnog stabla i potrebno je da popunimo svaki sljedeći pokazivač čvora na njegov sljedeći desni čvor. Ako nema sledećeg…

Čitaj više

Izbrišite čvorove i vratite Forest Leetcode rješenje

Iskaz problema Rešenje LeetCode brisanja čvorova i vraćanja šume – „Izbriši čvorove i vrati šumu“ navodi da je dat koren binarnog stabla gde svaki čvor ima različitu vrednost. Također nam je dat niz, to_delete, gdje trebamo izbrisati sve čvorove sa vrijednostima sadržanim u…

Čitaj više

Oporavak binarnog stabla pretraživanja Leetcode rješenje

Iskaz problema Recover Binary Search Tree LeetCode Rešenje – „Oporavak binarnog stabla pretrage“ navodi da je dat koren binarnog stabla pretrage, gde su vrednosti tačno dva čvora zamenjene greškom. Moramo oporaviti stablo bez promjene njegove strukture. Primjer: Ulaz: root = [1,3,null,null,2] Izlaz: [3,1,null,null,2] …

Čitaj više

Simetrično drvo Leetcode rješenje

Iskaz problema Rešenje LeetCode simetričnog stabla – „Simetrično stablo“ navodi da je dat koren binarnog stabla i da moramo da proverimo da li je dato binarno stablo ogledalo samog sebe (simetrično oko svog centra) ili nije? Ako je odgovor Da, moramo vratiti true u suprotnom, false. Primjer: …

Čitaj više

Translate »