Udhëzime hap pas hapi nga një nyje binar peme në një zgjidhje tjetër LeetCode

Deklarata e problemit: Udhëzime hap pas hapi nga një nyje binar peme në një tjetër zgjidhje LeetCode – Ju jepet rrënja e një peme binare me n nyje. Çdo nyje i është caktuar në mënyrë unike një vlerë nga 1 në n. Ju jepet gjithashtu një vlerë fillestare me numër të plotë që përfaqëson vlerën e nyjes fillestare s, dhe një vlerë tjetër e plotë e destinacionit që përfaqëson vlerën e destinacionit ...

Lexo më shumë

Përshkimi i rendit vertikal i zgjidhjes LeetCode të Pemës Binare

Paraqitja e problemit Përshkimi i rendit vertikal i pemës binare Zgjidhja e LeetCode thotë – Duke pasur parasysh rrënjën e një peme binare, llogaritni përshkimin e rendit vertikal të pemës binare. Për secilën nyje në pozicion (rresht, kolonë), fëmijët e saj majtas dhe djathtas do të jenë përkatësisht në pozicionet (rresht + 1, kolon - 1) dhe (rresht + 1, kolon + 1). …

Lexo më shumë

Shuma e numrave të rrënjës në gjethe Zgjidhje LeetCode

Deklarata e problemit Shuma nga rrënja te numrat e gjetheve LeetCode Solution thotë – Ju jepet rrënja e një peme binare që përmban vetëm shifra nga 0 në 9. Çdo shteg rrënjë-gjethe në pemë përfaqëson një numër. Për shembull, shtegu rrënjë me fletë 1 -> 2 -> 3 përfaqëson numrin 123. Ktheni shumën totale të të gjithë numrave rrënjë më fletë. Test…

Lexo më shumë

Zgjidhja e LeetCode për kalimin e renditjes së pemës binare

Paraqitja e problemit: Përshkimi i renditjes së pemës binare Zgjidhja e LeetCode Duke pasur parasysh rrënjën e një peme binare, ktheni kalimin e rendit të vlerave të nyjeve të saj. Shembulli 1: Hyrja: rrënjë = [1,null,2,3] Dalja: [1,3,2] Shembulli 2: Hyrja: rrënjë = [] Dalja: [] Shembulli 3: Hyrja: rrënja = [1] Dalja: [1] Kufizimet: Numri i nyjeve në…

Lexo më shumë

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur thotë se – Duke pasur parasysh root të një peme binare, rrafshoni pemën në një "listë të lidhur":

  • "Lista e lidhur" duhet të përdorë të njëjtën gjë TreeNode klasa ku right treguesi i fëmijës tregon në nyjen tjetër në listë dhe left treguesi i fëmijës është gjithmonë null.
  • "Lista e lidhur" duhet të jetë në të njëjtin rend si a para-qëllim përshkimi të pemës binare.

 

1 Shembull:

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhurinput:

 root = [1,2,5,3,4,null,6]

output:

 [1,null,2,null,3,null,4,null,5,null,6]

2 Shembull:

input:

 root = []

output:

 []

3 Shembull:

input:

 root = [0]

output:

 [0]

 

ALGORITMI -

IDE -

  • Për të rrafshuar një pemë binare, fillimisht do të gjejmë elementin më të djathtë të nënpemës së majtë dhe pasi të kemi marrë elementin më të djathtë, do të lidhim treguesin e djathtë të asaj nyje me një nënpemë të djathtë të një peme të caktuar.
  • Në hapin 2 ne do të lidhim treguesin e djathtë të nyjës rrënjë me nënpemën e majtë dhe do ta vendosim nënpemën e majtë si null.
  • Në hapin 3 tani nyja jonë rrënjë është një nyje e nënpemës së djathtë i njëjti proces do të ndodhë me këtë nyje dhe procesi do të vazhdojë akoma derisa të gjitha pjesët e majta të bëhen të pavlefshme.

Qasje për rrafshimin e pemës binare me zgjidhjen e kodit Leetcode të listës së lidhur -

– Në fillim, do të ekzekutoj një lak, dmth while(root != null) më pas do të marr dy variabla dhe do të ruaj nënpemën e majtë.

– pastaj do të kontrollojë kontrollin për nyjen më të djathtë të nënpemës së majtë duke përdorur while(k.left != null) dhe do ta lidhë atë nyje me nënpemën e djathtë duke përdorur (k.right = root.right).

– më pas lidhni treguesin e djathtë të nyjës rrënjë me nënpemën e majtë (root.djathtas = majtas) dhe vendosni treguesin e majtë të nyjes rrënjë si null (root.left=null) dhe do të përditësohet me (rrënjë = rrënjë.djathtas) kështu që tani rrënja është e drejtë nyja e nënpemës.

– ky proces do të vazhdojë derisa të gjitha pjesët e nënpemës së majtë të bëhen nënpema e djathtë. Prandaj, pema binare do të rrafshohet.

 

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Zgjidhja e 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

Zgjidhja Java:

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;
        }
    }
}

Kompleksiteti kohor: O(N)

Kompleksiteti i hapësirës: O (1)

Meqë kemi përshkuar vetëm një herë, kompleksiteti kohor do të jetë o(n).

dhe meqenëse nuk kemi zënë hapësirë ​​shtesë, kompleksiteti i hapësirës do të jetë o(1) hapësirë ​​shtesë konstante.

Pyetje e ngjashme - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Paraardhësi më i ulët i zakonshëm i zgjidhjes së kodit Leetcode të Pemës Binare

Deklarata e problemit Paraardhësi më i ulët i zakonshëm i një peme binare Zgjidhja LeetCode – “Paraardhësi më i ulët i zakonshëm i një peme binare” thotë se duke pasur parasysh rrënjën e pemës binare dhe dy nyjet e pemës. Ne duhet të gjejmë paraardhësin më të ulët të përbashkët të këtyre dy nyjeve. Më e ulëta e zakonshme…

Lexo më shumë

Popullimi i treguesve të ardhshëm djathtas në zgjidhjen e kodit Leetcode të çdo nyje

Deklarata e problemit Popullimi i treguesve të ardhshëm djathtas në çdo nyje Zgjidhja e LeetCode – “Popullimi i treguesve të ardhshëm djathtas në çdo nyje” thotë se duke pasur parasysh rrënjën e pemës së përsosur binare dhe ne duhet të plotësojmë çdo tregues tjetër të nyjës në nyjen tjetër të djathtë. Nëse nuk ka tjetër…

Lexo më shumë

Fshi nyjet dhe kthe Zgjidh Forest Leetcode

Deklarata e problemit Zgjidhja e fshirjes së nyjeve dhe pyllit të kthimit LeetCode - "Fshi nyjet dhe pyllin e kthimit" thotë se duke pasur parasysh rrënjën e pemës binare ku çdo nyje ka një vlerë të veçantë. Na jepet gjithashtu një grup, to_delete, ku duhet të fshijmë të gjitha nyjet me vlerat e përfshira në…

Lexo më shumë

Recover Binary Search Tree Leetcode Solution

Deklarata e problemit Recover Binary Search Tree LeetCode Solution – “Recover Binary Search Tree” thotë se duke pasur parasysh rrënjën e pemës së kërkimit binar, ku vlerat e saktësisht dy nyjeve janë ndërruar gabimisht. Ne duhet të rikuperojmë pemën pa ndryshuar strukturën e saj. Shembull: Hyrja: rrënjë = [1,3,null,null,2] Dalja: [3,1,null,null,2] …

Lexo më shumë

Translate »