Najkraći nesortirani kontinuirani podniz LeetCode rješenje

Najava problema Najkraći nesortirani kontinuirani podniz LeetCode Rješenje kaže da – Dati cijeli niz brojeva, morate pronaći jedan kontinuirani podniz koji ako sortirate samo ovaj podniz uzlaznim redoslijedom, onda će cijeli niz biti sortiran uzlaznim redoslijedom. Vrati dužinu najkraćeg podniza. Primjer 1: …

Čitaj više

Rectangle Overlap LeetCode Solution

Najava problema: Rectangle Overlap LeetCode Rješenje – kaže da je pravougaonik poravnat po osi predstavljen kao lista, [x1, y1, x2, y2], gdje je (x1, y1) koordinata njegovog donjeg lijevog ugla, a (x2 , y2) je koordinata njegovog gornjeg desnog ugla. Njena gornja i donja ivica su paralelne sa X-osom, a njena leva…

Čitaj više

Da li je Graf bipartitan? LeetCode Solution

Iskaz problema je Graf Bipartite LeetCode rješenje - Postoji neusmjeren graf sa n čvorova, gdje je svaki čvor numeriran između 0 i n – 1. Dat vam je 2D graf niza, gdje je graph[u] niz čvorova koji čvor u je u susjedstvu. Formalnije, za svaki v u grafu[u], postoji neusmjerena ivica između čvora u i čvora v. Graf ima ...

Čitaj više

Dizajn Dodajte i pretražite Words Strukturu podataka LeetCode Solution

Izjava o problemu: Dizajnirajte strukturu podataka za dodavanje i pretraživanje riječi LeetCode rješenje kaže – Dizajnirajte strukturu podataka koja podržava dodavanje novih riječi i pronalaženje da li se string poklapa sa bilo kojim prethodno dodatim nizom. Implementirajte klasu WordDictionary: WordDictionary() Inicijalizira objekt. void addWord(word) Dodaje riječ strukturi podataka, može se kasnije upariti. bool pretraga(riječ) Vraća true ako postoji…

Čitaj više

Rješenje za minimalnu sumu putanje Leetcode

Najava problema Minimalna suma putanje LeetCode rješenje – “Minimalna suma putanje” kaže da je data anxm mreža koja se sastoji od nenegativnih cijelih brojeva i da moramo pronaći putanju od gornjeg lijevog do donjeg desnog, što minimizira zbir svih brojeva duž putanje . Možemo samo da se krećemo…

Čitaj više

Minimalna cijena penjanja stepenicama LeetCode rješenje

Iskaz problema Minimalni trošak penjanja stepenicama LeetCode Rješenje – Dat je trošak cijelog niza, gdje je trošak[i] trošak i-og koraka na stepeništu. Kada platite troškove, možete se popeti na jednu ili dvije stepenice. Možete početi od koraka sa indeksom 0 ili od koraka sa…

Č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

Broj podnizova koji zadovoljavaju zadani zbirni uvjet rješenje LeetCode

Iskaz problema Broj podnizova koji zadovoljavaju dani zbirni uslov LeetCode rješenje – kaže da je dat niz cijelih brojeva nums i cjelobrojni cilj. Vraća broj nepraznih podnizova brojeva tako da je zbir minimalnog i maksimalnog elementa na njemu manji ili jednak cilju. Pošto odgovor može biti previše…

Č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

Translate »