Rezultat zagrade LeetCode Solution

Iskaz problema Rezultat zagrade LeetCode Solution kaže – Dat je uravnotežen niz zagrada s i vrati maksimalan rezultat. Rezultat uravnoteženog niza zagrada zasniva se na sljedećim pravilima: “()” ima rezultat 1. AB ima rezultat A + B, gdje su A i B uravnoteženi nizovi zagrada. (A) ima rezultat 2 * A, gdje je A ...

Č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

Rješenje za dekodiranje stringa Leetcode

Iskaz problema Rešenje za dekodiranje niza LeetCode – “Dekodiranje stringa” traži od vas da konvertujete kodirani niz u dekodirani niz. Pravilo kodiranja je k[kodirani_string], gdje se kodirani_string unutar uglastih zagrada ponavlja tačno k puta gdje je k pozitivan cijeli broj. Primjer: Ulaz: s = ”3[a]2[bc]” Izlaz: “aaabcbc” …

Č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

Dodaj dva broja II Leetcode rješenje

Iskaz problema Rešenje za dodavanje dva broja II LeetCode – „Dodaj dva broja II“ navodi da dve neprazne povezane liste predstavljaju dva nenegativna cela broja gde je najznačajnija cifra prva i svaki čvor sadrži tačno jednu cifru. Moramo sabrati dva broja i vratiti zbroj kao…

Čitaj više

Dnevne temperature Leetcode Solution

Iskaz problema Dnevne temperature Leetcode Rješenje: navodi da niz cijelih brojeva temperatura predstavlja dnevne temperature, vratite odgovor niza tako da je answer[i] broj dana koje morate čekati nakon i-tog dana da dobijete topliju temperaturu. Ako ne postoji budući dan za koji je to moguće, umjesto toga zadržite answer[i] == 0. …

Čitaj više

Minimalno uklanjanje da biste napravili valjane zagrade LeetCode rješenje

Iskaz problema Minimalno uklanjanje za pravljenje valjanih zagrada LeetCode rješenje – Dat vam je niz s od '(', ')' i mala slova engleska slova. Vaš zadatak je da uklonite minimalni broj zagrada ( '(' ili ')', na bilo kojoj poziciji) tako da rezultirajući niz zagrada bude …

Čitaj više

Rješenje za hvatanje kišnice Leetcode

Iskaz problema Rešenje LeetCode za zarobljavanje kišne vode – „Zarobljavanje kišnice“ navodi da je dat niz visina koji predstavlja mapu nadmorske visine gde je širina svake trake 1. Moramo pronaći količinu vode zarobljene nakon kiše. Primjer: Ulaz: visina = [0,1,0,2,1,0,1,3,2,1,2,1] Izlaz: 6 Objašnjenje: Provjerite …

Čitaj više

Važeće zagrade Leetcode Rješenje

Iskaz problema Ispravne zagrade LeetCode Rješenje – “Važeće zagrade” navode da vam je dat niz koji sadrži samo znakove '(', ')', '{', '}', '[' i ']'. Moramo utvrditi da li je ulazni niz ispravan ili ne. Za niz se kaže da je važeći niz ako se otvorene zagrade moraju zatvoriti…

Čitaj više

Rješenje za maksimalnu frekvenciju Leetcode

Izjava o problemu LeetCode rješenje za maksimalni frekvencijski stog – “Maksimalni stek frekvencija” traži od vas da dizajnirate stek frekvencija u kojem kad god izbacimo element iz steka, on bi trebao vratiti najčešći element prisutan u steku. Implementirajte klasu FreqStack: FreqStack() konstruira prazan stek frekvencija. void push(int val) gura…

Čitaj više

Translate »